比赛 20120323 评测结果 AWTAWWWWTT
题目名称 放棋子 最终得分 20
用户昵称 苏轼 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2012-03-23 21:35:06
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
int n,m,k,q[81]={0},ji1=0;
unsigned long long ji=1,answer=0,ans=0;
void dfs(int x);
int main()
{
	freopen ("examtwo.in","r",stdin);
	freopen ("examtwo.out","w",stdout);
	cin>>n>>m>>k;
	int a;
	a=n*m;
	for (int i=0;i<k;i++)
	{
		ji*=a;
		a--;
	}
	for (int i=2;i<=k;i++)
	{
		ji/=i;
	}
	dfs(1);
	int d,b;
	d=answer;
	b=ji;
	while(b^=d^=b^=d%=b);
	answer/=d;
	ji/=d;
	cout<<ji<<'/'<<answer;
	return 0;
}


void dfs(int x)
{
	if (ji1==k)
	{
		answer++;
		return;
	}
	for (int i=x;i<=n*m;i++)
	{
		if (i%n==1&&i!=1)
		{
			if (q[i-m]==1)
				continue;
		}
		else if (i<=m)
		{
			if (q[i-1]==1)
				continue;
		}
		else if (q[i-1]==1||q[i-m]==1)
		{
			continue;
		}
		q[i]=1;
		ji1++;
		dfs(i+1);
		ji1--;
		q[i]=0;
	}
}