M_sea

CF1051D Bicolorings
Luogu算法状压DP。那么设$f[i][j][k]$表示前i列,有j个联通块,第i列状态为k的方案数。容易得到:...
扫描右侧二维码阅读全文
03
2018/10

CF1051D Bicolorings

Luogu

算法

状压DP。

那么设$f[i][j][k]$表示前i列,有j个联通块,第i列状态为k的方案数。

容易得到:

$f[i][j][0]=f[i-1][j][0]+f[i-1][j][1]+f[i-1][j][2]+f[i-1][j-1][3]$

$f[i][j][1]=f[i-1][j-1][0]+f[i-1][j][1]+f[i-1][j-2][2]+f[i-1][j-1][3]$

$f[i][j][2]=f[i-1][j-1][0]+f[i-1][j-2][1]+f[i-1][j][2]+f[i-1][j-1][3]$

$f[i][j][3]+=f[i-1][j-1][0]+f[i-1][j][1]+f[i-1][j][2]+f[i-1][j][3]$

然后大力DP即可。

注意边界为$f[1][1][0]=f[1][2][1]=f[1][2][2]=f[1][1][3]=1$。

代码

#include <bits/stdc++.h>
#define re register
typedef int mainint;
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

const int MOD=998244353;

int n,k;
int f[1010][2010][4]; //f[i][j][k]表示前i列,有j个联通块,第i列状态为k的方案数 

mainint main() {
    n=read(),k=read();
    f[1][1][0]=f[1][1][3]=f[1][2][1]=f[1][2][2]=1;
    for (re int i=2;i<=n;i++)
        for (re int j=0;j<=k;j++) {
            (f[i][j][0]+=f[i-1][j][0]+f[i-1][j][1]+f[i-1][j][2]+f[i-1][j-1][3])%=MOD;
            (f[i][j][1]+=f[i-1][j-1][0]+f[i-1][j][1]+f[i-1][j-2][2]+f[i-1][j-1][3])%=MOD;
            (f[i][j][2]+=f[i-1][j-1][0]+f[i-1][j-2][1]+f[i-1][j][2]+f[i-1][j-1][3])%=MOD;
            (f[i][j][3]+=f[i-1][j-1][0]+f[i-1][j][1]+f[i-1][j][2]+f[i-1][j][3])%=MOD;
        }
    printf("%lld\n",(f[n][k][0]+f[n][k][1]+f[n][k][2]+f[n][k][3])%MOD);
    return 0;
}
最后修改:2019 年 05 月 26 日 03 : 02 PM

发表评论