CF1051D 题解

· · 题解

题目传送门

思路

可以使用动态规划解决此题。

首先定义状态转移数组 f。首先定义 z 为两排棋盘上的颜色在二进制下的结果。再定义 f_{i,j,z} 的含义为：在第 i 列，有着 j 个连通块，状态为 z 下的染色方案数。

可以将 z 的 4 种状态分别转移求数量和，初始化 f_{1,1,1}，f_{1,1,2}，f_{1,2,0} 和 f_{1,2,3} 为 1，表示起点有 1 种方案。用 i 作列数枚举从 2 到 n，j 枚举连通块从 0 到 k。状态转移方程是它各个连通块染色方案数的总和，即为：

f_{i,j,0}=f_{i-1,j,0}+f_{i-1,j-1,1}+f_{i-1,j-1,2}+f_{i-1,j-2,3}\\ f_{i,j,1}=f_{i-1,j,0}+f_{i-1,j,1}+f_{i-1,j-1,2}+f_{i-1,j,3}\\ f_{i,j,2}=f_{i-1,j,0}+f_{i-1,j-1,1}+f_{i-1,j,2}+f_{i-1,j,3}\\ f_{i,j,3}=f_{i-1,j-2,0}+f_{i-1,j-1,1}+f_{i-1,j-1,2}+f_{i-1,j,3} \end{cases}

最后输出 f_{n,k,0}+f_{n,k,1}+f_{n,k,2}+f_{n,k,3} 即为答案。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=1e3+10,MOD=998244353;
long long f[N][N*2][4];
int main(){
    int n=read(),k=read();
    f[1][1][1]=f[1][1][2]=f[1][2][0]=f[1][2][3]=1ll;
    for(int i=2;i<=n;++i)
        for(int j=0;j<=k;++j){
            f[i][j][0]=(f[i-1][j][0]+f[i-1][j-1][1]+f[i-1][j-1][2]+f[i-1][j-2][3])%MOD;
            f[i][j][1]=(f[i-1][j][0]+f[i-1][j][1]+f[i-1][j-1][2]+f[i-1][j][3])%MOD;
            f[i][j][2]=(f[i-1][j][0]+f[i-1][j-1][1]+f[i-1][j][2]+f[i-1][j][3])%MOD;
            f[i][j][3]=(f[i-1][j-2][0]+f[i-1][j-1][1]+f[i-1][j-1][2]+f[i-1][j][3])%MOD;
        }
    printf("%d\n",(f[n][k][0]+f[n][k][1]+f[n][k][2]+f[n][k][3])%MOD);
    return 0;
}