【Codeforces 1051D】Bicolorings

【链接】 我是链接,点我呀:)
【题意】

题意

【题解】

dp[i][j][k]表示前i列,有j个联通块下,最后一列的状态为k的方案数
k如果为1的话,表示最后一列两个块不一样,k如果为0表示一样
枚举最后一列的情况转移就好

【代码】

#include <bits/stdc++.h>
using namespace std;
const int maxn=1100;
const long long mod=998244353;
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
ll dp[maxn][2*maxn][2],n,m;
int main(){
    int i,j;
    mem(dp,0);
    scanf("%I64d%I64d",&n,&m);
    dp[1][2][1]=2;dp[1][1][0]=2;
    for(i=2;i<=n;i++){
        for(j=1;j<=m;j++){
            dp[i][j][0]+=2*dp[i-1][j][1]+dp[i-1][j-1][0]+dp[i-1][j][0];
            dp[i][j][0]%=mod;
            dp[i][j][1]+=2*dp[i-1][j-1][0]+dp[i-1][j-2][1]+dp[i-1][j][1];
            dp[i][j][1]%=mod; 
        }
    }
    ll ans=(dp[n][m][0]+dp[n][m][1])%mod;
    printf("%I64dn",ans);
    return 0;
}