2 seconds
256 megabytes
standard input
standard output
You are given a grid, consisting of $$$2$$$ rows and $$$n$$$ columns. Each cell of this grid should be colored either black or white.
Two cells are considered neighbours if they have a common border and share the same color. Two cells $$$A$$$ and $$$B$$$ belong to the same component if they are neighbours, or if there is a neighbour of $$$A$$$ that belongs to the same component with $$$B$$$.
Let's call some bicoloring beautiful if it has exactly $$$k$$$ components.
Count the number of beautiful bicolorings. The number can be big enough, so print the answer modulo $$$998244353$$$.
The only line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 1000$$$, $$$1 \le k \le 2n$$$) — the number of columns in a grid and the number of components required.
Print a single integer — the number of beautiful bicolorings modulo $$$998244353$$$.
3 4
12
4 1
2
1 2
2
One of possible bicolorings in sample $$$1$$$:
$$$(i,k,0)$$$ 的矩阵，可以由 $$$i-1$$$ 列的矩阵添加一列 $$$00$$$ 得到，当它的结尾为 $$$00$$$, $$$01$$$, $$$10$$$, $$$11$$$时，分别会让连通块个数：不变，不变，不变，+1,所以 $$$(i,k,0)$$$由 $$$(i-1,k,0)$$$, $$$(i-1,k,1)$$$, $$$(i-1,k,2)$$$, $$$(i-1,k-1,3)$$$得到：
$$$$$$
\begin{align}
dp[i][k][0,0]=~~~& dp[i-1][k][0,0]\\
+& dp[i-1][k][0,1]\\
+& dp[i-1][k][1,0]\\
+& dp[i-1][k-1][1,1]
\end{align}
$$$$$$
$$$(i,k,1)$$$的矩阵同理，为$$$i-1$$$列的矩阵添加 $$$01$$$，当结尾为 $$$00$$$, $$$01$$$, $$$10$$$, $$$11$$$时，分别会使连通块的个数：+1，不变，+2，+1，所以$$$(i,k,1)$$$由$$$(i-1,k-1,0)$$$,$$$(i-1,k,1)$$$,$$$(i-1,k-2,2)$$$,$$$(i-1,k-1,3)$$$得到：
$$$$$$
\begin{align}
dp[i][k][0,1]=~~~& dp[i-1][k-1][0,0]\\
+& dp[i-1][k][0,1]\\
+& dp[i-1][k-2][1,0]\\
+& dp[i-1][k-1][1,1]
\end{align}
$$$$$$
(i,k,2)同理可得：
$$$$$$
\begin{align}
dp[i][k][1,0]=~~~& dp[i-1][k-1][0,0]\\
+& dp[i-1][k-2][0,1]\\
+& dp[i-1][k][1,0]\\
+& dp[i-1][k-1][1,1]
\end{align}
$$$$$$
(i,k,3)同理可得：
$$$$$$
\begin{align}
dp[i][k][1,1]=~~~& dp[i-1][k-1][0,0]\\
+& dp[i-1][k][0,1]\\
+& dp[i-1][k][1,0]\\
+& dp[i-1][k][1,1]
\end{align}
$$$$$$
于是得到了完整的递推公式，只需要从下面的状态开始，
$$$$$$
\begin{align}
dp[1][1][0,0]=1\\
dp[1][2][0,1]=1\\
dp[1][2][1,0]=1\\
dp[1][1][1,1]=1
\end{align}
$$$$$$
就能推到出所有的状态，最后对dp[n][k]的所有情况求和就是答案了。
注意当k为1时，是不存在k-2的状态的，需要特判一下避免超出数组范围
#include<stdio.h>
typedef long long LL;
#define mod 998244353
int dp[][][] = {};
int main() {
int n, lm;
scanf("%d %d", &n, &lm);
//初始化
dp[][][] = ;//
dp[][][] = ;//
dp[][][] = ;//
dp[][][] = ;//
LL temp=;
for (int i = ; i <= n; ++i) {
for (int k = ; k <= (i << ); ++k) {
temp = ;//使用temp求和来避免溢出
temp =temp
+ dp[i - ][k][]//
+ dp[i - ][k][]//
+ dp[i - ][k][]//
+ dp[i - ][k - ][];//
dp[i][k][] = temp % mod;
temp = ;
temp = temp
+ dp[i - ][k][]//
+ dp[i - ][k-][]//
+ (k>=?dp[i - ][k - ][]:)//
+ dp[i - ][k-][];//
dp[i][k][] = temp%mod;
temp = ;
temp = temp
+ (k>=?dp[i - ][k - ][]:)//
+ dp[i - ][k-][]//
+ dp[i - ][k][]//
+ dp[i - ][k-][];//
dp[i][k][] = temp%mod;
temp = ;
temp = temp
+ dp[i - ][k][]//
+ dp[i - ][k - ][]//
+ dp[i - ][k][]//
+ dp[i - ][k][];//
dp[i][k][] = temp%mod;
temp = ;
}
}
LL ans = ;
ans = ans + dp[n][lm][] + dp[n][lm][] + dp[n][lm][] + dp[n][lm][];
ans = ans%mod;
printf("%I64d\n", ans);
}