题意

给一个2行n列的矩阵填上黑色和白色，求连通块个数为k个的填色方案数量(mod 998244353)

分析

因为只有两行，为n-1列的矩阵增加1列的情况数只有很少，容易想到用 $$$(i, k)$$$ 表示 $$$i$$$ 列有 $$$k$$$ 个连通块的矩阵， 但是它在向 $$$i+1$$$ 列的矩阵转移时，需要知道最后一列的状态，所以可以用 $$$0$$$, $$$1$$$, $$$2$$$, $$$3$$$表示最后一列为 $$$00$$$, $$$01$$$, $$$10$$$, $$$11$$$，那么状态就增加一维变成 $$$(i, k, s)$$$，然后就是分析递推关系：

$$$(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);

}