题意：
给出一个2*n的矩形，你可以往里面填色。有黑和白两种颜色，会形成连通块（黑连通块和白连通块都算连通块）。询问有多少种填色情况使得连通块的数量有k个。
题解：
考试的时候没想出来，其实就是一个简单的线性DP。具体看代码。
//dp[i][j][k]表示到第i列，有j个块， 最后一列的情况是k //这里00是0，01是1，10是2，11是3 #include<bits/stdc++.h> using namespace std; const int maxn=1005; const int mod=998244353; typedef long long ll; ll dp[maxn][maxn*2][4]; int main () { int n,k; cin>>n>>k; dp[1][1][0]=1; dp[1][1][3]=1; dp[1][2][1]=1; dp[1][2][2]=1; for (int i=1;i<=n;i++) { for (int j=1;j<=2*n;j++) { dp[i][j][0]=dp[i][j][0]+dp[i-1][j][1],dp[i][j][0]%=mod; dp[i][j][0]=dp[i][j][0]+dp[i-1][j][2],dp[i][j][0]%=mod; dp[i][j][0]=dp[i][j][0]+dp[i-1][j][0],dp[i][j][0]%=mod; dp[i][j][0]=dp[i][j][0]+dp[i-1][j-1][3],dp[i][j][0]%=mod; dp[i][j][1]=dp[i][j][1]+dp[i-1][j-1][0],dp[i][j][1]%=mod; dp[i][j][1]=dp[i][j][1]+dp[i-1][j-1][3],dp[i][j][1]%=mod; dp[i][j][1]=dp[i][j][1]+dp[i-1][max(0,j-2)][2],dp[i][j][1]%=mod; dp[i][j][1]=dp[i][j][1]+dp[i-1][j][1],dp[i][j][1]%=mod; dp[i][j][2]=dp[i][j][2]+dp[i-1][j-1][0],dp[i][j][2]%=mod; dp[i][j][2]=dp[i][j][2]+dp[i-1][j-1][3],dp[i][j][2]%=mod; dp[i][j][2]=dp[i][j][2]+dp[i-1][max(0,j-2)][2],dp[i][j][2]%=mod; dp[i][j][2]=dp[i][j][2]+dp[i-1][j][2],dp[i][j][2]%=mod; dp[i][j][3]=dp[i][j][3]+dp[i-1][j-1][0],dp[i][j][3]%=mod; dp[i][j][3]=dp[i][j][3]+dp[i-1][j][1],dp[i][j][3]%=mod; dp[i][j][3]=dp[i][j][3]+dp[i-1][j][2],dp[i][j][3]%=mod; dp[i][j][3]=dp[i][j][3]+dp[i-1][j][3],dp[i][j][3]%=mod; } } ll ans=0; for (int i=0;i<4;i++) ans+=dp[n][k][i],ans%=mod; printf("%lld\n",ans); }
原文：https://www.cnblogs.com/zhanglichen/p/13212710.html