Bicolorings

题目链接

题意

有一个2*n的格子，每个格子可以涂成白色或黑色，然后 根据涂完的颜色可以分成连通块（白色跟白色连通，黑色跟黑色联通）然后 问连通块的数量是k的时候有多少种涂法。。
我还是菜了啊
想不到dp数组表示啥，想到了这个题就很简单了。

题解：

dp[1000][2000][4] 。
n是1000
k是2000
后面的4 表示 这竖上面是啥 00 01 10 11 这四种。
把二维变成一维 ，秒啊~~
dp[i][j][p] 表示 到第i列是p连通块为j的有多少种。
状态转移就很好算了。简单又暴力。。就不用说了。

代码:

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 1005;
typedef long long ll;
// 00 01 10 11
ll dp[maxn][2 * maxn][4];
const ll mod = 998244353;

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