记录编号	489942	评测结果	AAAAAAAAAA
题目名称	放棋子	最终得分	100
用户昵称	WHZ0325	是否通过	通过
代码语言	C++	运行时间	0.059 s
提交时间	2018-03-06 15:00:21	内存使用	0.57 MiB

#include <cstdio>
#include <algorithm>
#include <vector>
typedef long long int ll;
int gcd(ll a,ll b) {
	return b==0?a:gcd(b,a%b);
}
inline ll c(int n,int m) {
	ll c=1;
	for(int k=1;k<=m;++k) {
		c=c*(n-k+1)/k;
	}
	return c;
}
int n,m,pn;
ll f[2][1<<10][21];
std::vector<int> state;
std::vector<int> cnt;
int main() {
	freopen("examtwo.in","r",stdin);
	freopen("examtwo.out","w",stdout);
	scanf("%d%d%d",&n,&m,&pn);
	if(n<m) std::swap(n,m);
	int temp;
	for(int i=0;i<(1<<m);++i) {
		if(((i<<1)&i)==0) {
			temp=0;
			for(int j=0;j<m;++j) {
				if((i>>j)&1) ++temp;
			}
			state.push_back(i);
			cnt.push_back(temp);
		}
	}
	for(unsigned int i=0;i<state.size();++i) {
		if(pn-cnt[i]>=0) f[0][i][pn-cnt[i]]=1;
	}
	for(int i=2;i<=n;++i) {
		for(unsigned int j=0;j<state.size();++j) {
			for(int k=0;k+cnt[j]<=pn;++k) {
				f[(i+1)%2][j][k]=0;
				for(unsigned int l=0;l<state.size();++l) {
					if((state[j]|state[l])==(state[j]^state[l])) {
						f[(i+1)%2][j][k]+=f[i%2][l][k+cnt[j]];
					}
				}
			}
		}
	}
	ll x=c(n*m,pn),y=0;
	for(unsigned int i=0;i<state.size();++i) {
		y+=f[(n+1)%2][i][0];
	}
	int g=gcd(x,y);x/=g;y/=g;
	printf("%lld/%lld\n",x,y);
	fclose(stdin);
	fclose(stdout);
	return 0;
}