记录编号	536439	评测结果	WEEEEEEEEE
题目名称	放棋子	最终得分	0
用户昵称	Deacep	是否通过	未通过
代码语言	C++	运行时间	1.276 s
提交时间	2019-07-07 17:33:02	内存使用	13.75 MiB

#include<bits/stdc++.h>
using namespace std;//si lian tong
int n,m;
int lim;
int ind[1<<9];
int sum[1<<9];
int f[2][1<<9][21];//current
int cnt=0;
void swap(int &x,int &y){
	int t=x;
	x=y;
	y=t;
}
int jc(int p){
	if(!p)
	return 1;
	return p*jc(p-1);
}
int c(int i,int j){
	int t=jc(j)/jc(j-i);
	return t/jc(i);
}
int gcd(int p,int q){
	return !p?q:gcd(q%p,p);
}
int main(){
	memset(f,0,sizeof(f));
	freopen("examtwo.in","r",stdin);
	freopen("examtwo.out","w",stdout);
	cin>>n>>m>>lim;
	if(n<m)
	swap(n,m);
	for(int i=0;i<(1<<m);i++){
		if(!(i&(i<<1))){
			ind[++cnt]=i;
			int j=i;
			while(j){
				j-=j&(-j);
				sum[cnt]++;
			}
		}
	}
	f[0][1][0]=1;
	//for(int i=1;i<=cnt;i++)
	//f[0][i][sum[i]]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=cnt;j++){//pr
			for(int k=1;k<=cnt;k++){//las
				for(int l=sum[j];l<=lim;l++){
					if((!(ind[j]&ind[k]))&&l-sum[j]>=sum[k]){
						f[i&1][j][l]+=f[1-i&1][k][l-sum[j]];
					}
				}
			}
		}
		memset(f[1-i&1],0,sizeof(f[1-i&1]));
	}//以下是有问题的一部分 
	int ans=0;
	for(int i=1;i<=cnt;i++)
	ans+=f[n&1][i][lim];
	int s=c(lim,n*m);
	int est=gcd(ans,s);
	cout<<s/est<<'/'<<ans/est;
	return 0;
}