比赛 郑州市创意编程大赛复现赛 评测结果 ATTTTTTTTT
题目名称 小象 最终得分 10
用户昵称 健康铀 运行时间 18.145 s
代码语言 C++ 内存使用 27.19 MiB
提交时间 2024-11-25 20:21:42
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lst now^1
#define debug cout<<"flyfree\n";
inline ll read(){
	ll x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
ll dp[3][1<<20];
ll now,n,k,ans;
int main(){
	freopen("bishops.in","r",stdin);
	freopen("bishops.out","w",stdout);
	while(1){
	n=read(),k=read();
		if(!n&&!k)break;
	now=1;
	ans=0;
	memset(dp,0,sizeof(dp));
	dp[1][0]=1;
	for(int i=1;i<=n*2-1;i++){
		now=lst;
		for(int j=0;j<(1<<(2*n-1));j++){
			dp[now][j]=dp[lst][j];
		}
		for(int j=abs(n-i)+1;j<=n*2-abs(n-i);j+=2){
			for(int u=0;u<(1<<(2*n-1));u++){
				if(!dp[lst][u])continue;
				if(u&(1<<j-1))continue;
				ll y=u|(1<<j-1);
				dp[now][y]+=dp[lst][u];
			}
		}
	}
	for(int i=0;i<(1<<(2*n-1));i++){
		if(__builtin_popcount(i)==k)ans+=dp[now][i];
	}
	cout<<ans<<endl;
	}
	return 0;
}