题解：CF1051D Bicolorings

Pyrf_uqcat · 2025-03-08 21:07:02 · 题解

动态规划，很有思维含量。

首先看到题还以为打表找规律，但是规律好像是没有的。

注意到棋盘宽为二，那每次往右边摆两个就有四种方式：黑黑，黑白，白黑，白白。那就可以将 dp_{i,j,k} 表示为前 i 列有 j 个连通块时当前为第 k 种摆法的方案数。

初始化：

dp[1][1][1]=1;
dp[1][2][2]=1;
dp[1][2][3]=1;
dp[1][1][4]=1;

转移方式推的时候可以画图便于推式：

//1:X 2:X 3:. 4:.
//X   .   X   .
dp[i][j][1]+=dp[i-1][j][1]+dp[i-1][j][2]+dp[i-1][j][3]+dp[i-1][j-1][4];
dp[i][j][2]+=dp[i-1][j-1][1]+dp[i-1][j][2]+dp[i-1][j-2][3]+dp[i-1][j-1][4];
dp[i][j][3]+=dp[i-1][j-1][1]+dp[i-1][j-2][2]+dp[i-1][j][3]+dp[i-1][j-1][4];
dp[i][j][4]+=dp[i-1][j-1][1]+dp[i-1][j][2]+dp[i-1][j][3]+dp[i-1][j][4];

答案就是将所有最后列都加起来。

代码

#define max(a,b) (a)>(b)?(a):(b)
#define min(a,b) (a)<(b)?(a):(b)
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N=1e3+5;
const int mod=998244353;

int n,k;

int dp[N][2*N][5];

inline void init()
{
    dp[1][1][1]=1;
    dp[1][2][2]=1;
    dp[1][2][3]=1;
    dp[1][1][4]=1;
}

signed main()
{
    cin>>n>>k;
    init();
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=k;j++)
        {
//          1:X 2:X 3:. 4:.
//            X   .   X   .
            dp[i][j][1]+=dp[i-1][j][1]+dp[i-1][j][2]+dp[i-1][j][3]+dp[i-1][j-1][4];
            dp[i][j][2]+=dp[i-1][j-1][1]+dp[i-1][j][2]+dp[i-1][j-2][3]+dp[i-1][j-1][4];
            dp[i][j][3]+=dp[i-1][j-1][1]+dp[i-1][j-2][2]+dp[i-1][j][3]+dp[i-1][j-1][4];
            dp[i][j][4]+=dp[i-1][j-1][1]+dp[i-1][j][2]+dp[i-1][j][3]+dp[i-1][j][4];
            dp[i][j][1]%=mod,dp[i][j][2]%=mod,dp[i][j][3]%=mod,dp[i][j][4]%=mod;
//          cout<<i<<' '<<j<<' '<<dp[i][j][1]<<' '<<dp[i][j][2]<<' '<<dp[i][j][3]<<' '<<dp[i][j][4]<<endl;
        }
    }
    int ans=0;
    for(int i=1;i<=4;i++)
    {
        ans+=dp[n][k][i];
        ans%=mod;
    }
    cout<<ans<<endl;
    return 0;
}