Bicolorings（DP）

Bicolorings

Educational Codeforces Round 51 (Rated for Div. 2)https://codeforces.com/problemset/problem/1051/D

---

题目大意：
给出$2$2行$n$n列的网格，每个格子涂黑或涂白，l两个相邻的格子如果颜色相同则说他们在一个区域，如果颜色不同则是两个区域，求这个网格分成$k$k个区域的方案数。答案对$998244353$998244353取模。

思路：
动态规划。
2行n列的方格，从2行1列的方格开始，一列一列的增加，会发现，每新增加一列，只会与前一列的状态有关，这样自然会想到DP。考虑到条件不仅有列、划分的区域，还有列的状态，定义数组$dp[i][j][k]$dp[i][j][k]表示前 $i$i 列分成 $j$j 个区域且第 $i$i 列为第 $k$k 种放置方法的总的方案数，$k=0$k=0 表示第 $i$i 列放同一种颜色（全黑或全白），$k=1$k=1 表示第 $i$i 列放不同的颜色（上黑下白 或 上白下黑）。其实细分可以分成括号里写的四种情况，不过他们对答案的贡献是一样的，所以可以划分成两种。

Code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll mod = 998244353;
const int maxn = 1000 + 5;

ll dp[maxn][maxn << 1][2]; //dp[i][j][k]前i列分成j个区域且第i列为第k种放置方法的方案数
// 可以分成两种放法，i列最大可以有 i*2 个区域
// 0 - 第i列放同一种颜色
// 1 - 第i列放不同的颜色

/**
 * dp[i][j][0] = dp[i-1][j][1]*2 + dp[i-1][j][0] + dp[i-1][j-1][0];
 * dp[i][j][1] = dp[i-1][j-1][0]*2 + dp[i-1][j][1] + dp[i-1][j-2][1];
 */

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