比赛 SBOI虎年首秀 评测结果 WWTWWWWTTT
题目名称 放棋子 最终得分 0
用户昵称 䱖虁職 运行时间 5.002 s
代码语言 C++ 内存使用 4.09 MiB
提交时间 2022-02-23 20:02:59
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
typedef __int128 ll;
ll n,m,pn,vis[85][85]={0};
ll fm,fz=0;
inline ll read()
{
    ll x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
inline void write(ll a)
{
    if(a<0)
    {
        putchar('-');
        a=-a;
    }
    if(a>9)write(a/10);
    putchar(a%10+'0');
}
ll gcd(ll a,ll b)
{
    if(a%b==0)
        return b;
    return gcd(b,a%b);
}
ll j(ll x,ll y)
{
    if(x>=1&&x<=n&&y>=1&&y<=m)
        return 1;
    return 0;
}
void v(ll x,ll y,ll num)
{
    vis[x][y]+=num;
    vis[x][y+1]+=num;
    vis[x][y-1]+=num;
    vis[x+1][y]+=num;
    vis[x-1][y]+=num;
}
ll jc(ll a)
{
    ll ans=1;
    for(ll i=1;i<=a;i++)ans*=i;
    return ans;
}
ll C(ll n,ll m)
{
    ll ans=1;
    for(ll i=n+1;i<=m;i++)
        ans*=i;
    ans/=jc(n);
    return ans;
}
ll dfs(ll num)
{
    if(num>pn)
    {
        fz++;
        return 0;
    }
    else
    {
        for(ll tx=1;tx<=n;tx++)
        {
            for(ll ty=1;ty<=m;ty++)
            {
                if(vis[tx][ty]==0)
                {
                    for(ll k=0;k<=1;k++)
                    {
                        if(k==1)
                        {
                            v(tx,ty,1);
                            dfs(num+1);
                            v(tx,ty,-1);
                        }
                    }
                }
            }
        }
        return 0;
    }
}

int main(){
    freopen("examtwo.in","r",stdin);
    freopen("examtwo.out","w",stdout);
    n=read(),m=read(),pn=read();
    fm=C(pn,n*m);
    dfs(1);
    fz/=jc(pn);
    int g=gcd(fm,fz);
    fm/=g,fz/=g;
    write(fm),putchar('/'),write(fz),puts("");
    return 0;
}