题目链接:https://codeforces.com/problemset/problem/1051/D
题目大意:
有两行格子长度为n,每个格子可以涂成白色或者黑色。如果两个格子颜色相同并且相邻那他们就属于同一个联通块。现在问你有多少中涂色方案使联通块=k mod=998244353。

思路:

第i行只与第i-1行的状态有关。用f[i][j][k]:表示第i行有j个联通块。最右端的状态为k的方案数,就直接dp就可以了。

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int mod = 998244353;

LL f[1005][2005][4]={0};
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    f[1][2][0]=1;
    f[1][2][1]=1;
    f[1][1][2]=1;
    f[1][1][3]=1;
    for(int i=2; i<=n; i++){
        for(int j=1; j<=k; j++){
            for(int k=0; k<4; k++){
                if(k==0){
                    f[i][j][k]+=f[i-1][j][0];
                    f[i][j][k]+=f[i-1][j-2][1];
                    f[i][j][k]+=f[i-1][j-1][2];
                    f[i][j][k]+=f[i-1][j-1][3];
                }
                if(k==1){
                    f[i][j][k]+=f[i-1][j][1];
                    f[i][j][k]+=f[i-1][j-2][0];
                    f[i][j][k]+=f[i-1][j-1][2];
                    f[i][j][k]+=f[i-1][j-1][3];
                }
                if(k==2){
                    f[i][j][k]+=f[i-1][j][0];
                    f[i][j][k]+=f[i-1][j][1];
                    f[i][j][k]+=f[i-1][j][2];
                    f[i][j][k]+=f[i-1][j-1][3];
                }
                if(k==3){
                    f[i][j][k]+=f[i-1][j][0];
                    f[i][j][k]+=f[i-1][j][1];
                    f[i][j][k]+=f[i-1][j][3];
                    f[i][j][k]+=f[i-1][j-1][2];
                }
                f[i][j][k]%=mod;
            }
        }
    }
    LL ans=0;
    for(int i=0; i<4; i++){
        ans+=f[n][k][i];
    }
    printf("%lld\n", ans%mod);

    return 0;
}