比赛 20120323 评测结果 AAAAAAAAAA
题目名称 放棋子 最终得分 100
用户昵称 恢复用户698 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2012-03-23 21:31:35
显示代码纯文本
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

const int	MAX_N	= 80 + 10;
const int	MAX_S	= 1 << 9;
const int	MAX_K	= 20 + 10;

int			N, M, K, S;
long long	c		[MAX_N][MAX_K];
int			cnt		[MAX_S];
long long	f		[MAX_N][MAX_K][MAX_S];

int Calc(int x)
{
	int ans = 0;
	for(; x; x >>= 1)
		if (x & 1) ++ ans;
	return ans;
}

void Init()
{
	scanf("%d%d%d", &N, &M, &K);
	if (N <= M) swap(N, M);
	S = 1 << M;
	for(int i = 0; i < S; ++ i) cnt[i] = Calc(i);
	int p = N * M;
	if (K > p) {
		puts("0/0");
		exit(0);
	}
	c[0][0] = 1;
	for(int i = 1; i <= p; ++ i) {
		c[i][0] = 1;
		for(int j = 1; j <= K; ++ j)
			c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
	}
	f[0][0][0] = 1;
}

long long gcd(long long a, long long b)
{
	return ! b ? a : gcd(b, a % b);
}

void Solve()
{
	long long ans = 0, k, w;
	for(int i = 0; i < N; ++ i)
		for(int j = 0; j <= K; ++ j)
			for(int s = 0; s < S; ++ s)
				if (f[i][j][s]) {
					for(int ns = 0; ns < S; ++ ns)
						if ((s & ns) == 0 && (ns & (ns >> 1)) == 0) 
							f[i + 1][j + cnt[ns]][ns] += f[i][j][s];
				}
	for(int s = 0; s < S; ++ s)
		ans += f[N][K][s];
	k = c[N * M][K];
	w = gcd(k, ans);
	cout << k / w << '/' << ans / w << endl;
}

int	main()
{
	freopen("examtwo.in", "r", stdin);
	freopen("examtwo.out", "w", stdout);
	Init();
	Solve();
	return 0;
}