记录编号	581607	评测结果	AAAAAAAAAA
题目名称	放国王	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2023-08-08 16:16:51	内存使用	0.00 MiB

#include <bits/stdc++.h>
using namespace std;
const int N = (1<<10)+10,M = 110;
int n,m;
long long f[2][N][M],ans;
int s[N],cnt[N],u[N];
void sou(int x,int la,int now,int Cnt){
	if(x == n){
		s[0]++;
	    s[s[0]] = now,cnt[s[0]] = Cnt;
		return;
	}
	sou(x+1,0,now<<1,Cnt);
	if(!la)sou(x+1,1,(now<<1)+1,Cnt+1); 
}
int main(){
	freopen("placeking.in","r",stdin);
	freopen("placeking.out","w",stdout);
	scanf("%d%d",&n,&m);
	sou(0,0,0,0);
	for(int i = 1;i <= s[0];i++){
	    for(int j = 0;j < n;j++){
	    	int t = (1<<j);
	    	if(s[i] & t)
	    		u[i] |= t | (t<<1) | (t>>1);
		}
	}
	f[0][1][0] = 1;
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= s[0];j++){
			for(int k = cnt[j];k <= m;k++){
				for(int p = 1;p <= s[0];p++){
					if(!(s[p]&u[j]) && k-cnt[j] >= cnt[p]){
						f[i&1][j][k] += f[(i-1)&1][p][k-cnt[j]];
					}
				}
			}
		}
		memset(f[(i-1)&1],0,sizeof(f[(i-1)&1]));
	}
	for(int i = 1;i <= s[0];i++)ans += f[n&1][i][m];
	printf("%lld\n",ans);
	
	return 0;
	
}