自动搬运

查看原文

来自洛谷，原作者为

	wmy_goes_to_thu 菜

搬运于2025-08-24 22:27:01，当前版本为作者最后更新于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;
}