记录编号	38678	评测结果	AAAAAAAAAA
题目名称	放棋子	最终得分	100
用户昵称	Czb。	是否通过	通过
代码语言	C++	运行时间	0.072 s
提交时间	2012-06-01 17:11:31	内存使用	1.02 MiB

/*
UID:cheepok
PID:examtwo
*/
 
#include<stdio.h>
#include<vector>
 
using namespace std;
 
typedef long long Int;
 
struct orz
{Int x,y;};
 
Int n,m,s,t,x,y,f[100][21][300];
 
bool flag[10];
 
vector <orz> v;
 
void swap(Int &a,Int &b)
{a^=b^=a^=b;}
 
Int gcd(Int a,Int b)
{
    while(b^=a^=b^=a%=b);
    return a;
}
 
void dfs(int k)
{
    if(k>m){orz tmp;tmp.x=x;tmp.y=y;v.push_back(tmp);return;}
    y<<=1;dfs(k+1);if(!flag[k-1]){flag[k]=true;x++;y++;dfs(k+1);flag[k]=false;x--;}y>>=1;
}
 
int main()
{
    freopen("examtwo.in","r",stdin);
    freopen("examtwo.out","w",stdout);
    int i,j,k,l;scanf("%lld%lld%lld",&n,&m,&s);
    if(n<m)swap(n,m);dfs(1);t=v.size();
    f[0][0][0]=1;
    for(i=1;i<=n;i++)for(j=0;j<=s;j++)
    for(k=0;k<t;k++)for(l=0;l<t;l++)
    {if((v[k].y&v[l].y)==0&&v[k].x<=j)
    f[i][j][k]+=f[i-1][j-v[k].x][l];}
    x=n*m;y=1;for(i=0;i<s;i++)y*=x-i;
    for(i=2;i<=s;i++)y/=i;x=0;
    for(i=0;i<t;i++)x+=f[n][s][i];
    n=gcd(x,y);printf("%lld/%lld\n",y/n,x/n);
    return 0;
}