记录编号	532327	评测结果	AAAAAAAAAA
题目名称	放国王	最终得分	100
用户昵称	Hale	是否通过	通过
代码语言	C++	运行时间	0.018 s
提交时间	2019-05-28 19:46:16	内存使用	122.50 MiB

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=7e6+7;
LL tot,ans,cnt,n,k,sum;
LL state[N],f[11][200][121],king[N];
void init()
{
	tot=(1<<n)-1;
	for (int i=0;i<=tot;i++)
	{
		if (!((i<<1)&i))
		{
			state[++cnt]=i;
			int t=i;
			while(t)
			{
				king[cnt]+=t%2;
				t>>=1;	
			}
		}
	}
}
int main()
{
	freopen("placeking.in","r",stdin);
	freopen("placeking.out","w",stdout);
	scanf("%lld%lld",&n,&sum);
	init();
	for (int i=1;i<=cnt;i++)
	if (king[i]<=sum) f[1][i][king[i]]=1;
	for (int i=2;i<=n;i++)
	 for (int j=1;j<=cnt;j++)
	  for (int p=1;p<=cnt;p++)
	{
		if (state[j]&(state[p])) continue;
		if (state[j]&(state[p]<<1)) continue;
		if ((state[j]<<1)&state[p]) continue;
		for (int k=1;k<=sum;k++)
		{
			if (king[j]+k>sum) continue;
			f[i][j][king[j]+k]+=f[i-1][p][k];
		} 
	}
	for (int i=1;i<=n;i++)
	 for (int j=1;j<=cnt;j++)
	 ans+=f[i][j][sum];
	printf("%lld",ans);
	return 0;
}