文章目录
D. Bicolorings
题目链接:http://codeforces.com/contest/1051/problem/D
这道dp题分类讨论好多啊
dp[i][j][k]表示前 i 个格子,有 j个连通块,最后一列的状态是 k 的方案数
#include"bits/stdc++.h"
#define out(x) cout<<#x<<"="<<x
#define C(n,m) (m>n?0:(long long)fac[(n)]*invf[(m)]%MOD*invf[(n)-(m)]%MOD)
using namespace std;
typedef long long LL;
const int maxn=1e3+5;
const int MOD=998244353;
LL dp[maxn][maxn<<1][4];
int main()
{
dp[1][1][0]=1;
dp[1][1][3]=1;
dp[1][2][2]=1;
dp[1][2][1]=1;
for(int i=2; i<=1000; i++)
{
for(int j=1; j<=i*2; j++)
{
for(int k=0; k<=3; k++)
{
//连通块数量不变
dp[i][j][k]+=dp[i-1][j][k];//跟i-1的末尾的连通块状态一样
if(k==0||k==3)
{
dp[i][j][k]+=dp[i-1][j][k^1];//[2,3]
dp[i][j][k]+=dp[i-1][j][k^2];//[1,3]
}
//连通块数量增加一个
if(k==0||k==3)dp[i][j][k]+=dp[i-1][j-1][k^k];
else
{
dp[i][j][k]+=dp[i-1][j-1][0];
dp[i][j][k]+=dp[i-1][j-1][3];
}
//连通块数量增加两个
if(k==1||k==2)
{
if(j>=2)dp[i][j][k]+=dp[i-1][j-2][k^3];
}
dp[i][j][k]%=MOD;
}
}
}
int N,K;
while(cin>>N>>K)
{
LL ans=0;
for(int sta=0; sta<=3; sta++)ans+=dp[N][K][sta];
ans%=MOD;
cout<<ans<<endl;
}
}