题解 P7145 【[THUPC2021 初赛]合法序列】

wmy_goes_to_thu · 2020-12-22 19:58:22 · 题解

这题遇到二进制，当然想到状压 dp。

枚举前面 2^k 位的数，然后判断是否合法，如果合法就继续状压 dp，状态为 f_{i,j}，表示到第 i 个点后边 k 为为 j 的方案数。

复杂度其实不高，因为合法状态最多就几百个，2^k 只有 16，一共应该不过 10^7。

然后就过了：

#include<bits/stdc++.h>
using namespace std;
int f[16][505],r[16];
int main()
{
    int n,k,ans=0;
    cin>>n>>k;
    for(int i=0;i<(1<<k);i++)
    {
        for(int j=0;j<k;j++)r[i]|=((i>>j)&1)*(1<<(k-j-1));
    }
    for(int i=0;i<(1<<(1<<k));i++)
    {
        int flag=1;
        for(int j=0;j<=(1<<k)-k;j++)
        {
            int tt=(i>>j)&((1<<k)-1);
            tt=r[tt];
            if((i&(1<<tt)))continue;
            flag=0;
            break;
        }
        if(!flag)continue;
        memset(f,0,sizeof(f));
        f[i>>((1<<k)-k)][(1<<k)-1]=1;
        for(int j=1<<k;j<n;j++)for(int l=0;l<(1<<k);l++)
        {
            if((i&(1<<r[l]))==0)continue;
            int rrr=((l|(1<<k-1))^(1<<k-1))<<1;
            f[l][j]=(f[rrr|1][j-1]+f[rrr][j-1])%998244353;
        }
        int tr=0;
        for(int j=0;j<(1<<k);j++)tr=(tr+f[j][n-1])%998244353;
        ans=(ans+tr)%998244353;
    }
    cout<<ans<<endl;
    return 0;
}