比赛 SBOI虎年首秀 评测结果 AAAAAAAAAA
题目名称 放棋子 最终得分 100
用户昵称 yrtiop 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2022-02-23 19:40:51
显示代码纯文本
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
int n,m,k;
const int maxn = 1 << 10;
int SIT;
int state[maxn],tot,c[maxn];
ull f[2][21][maxn];
ull power(ull a,ull b) {
    ull ans = 1;
    for(;b;b >>= 1) {
        if(b & 1) {
            ans *= a;
        }
        a *= a;
    }
    return ans;
}
ull calc(ull x,ull y) {
    ull c = 1;
    for(int i = 1;i <= x;++ i) {
        c = c * (y - i + 1) / i; 
    }
    return c;
}
int lowbit(int x) {
    return x & -x;
}
void pre_solve() {
    for(int i = 0;i <= SIT;++ i) {
        if(i & (i >> 1))continue ;
        state[++ tot] = i;
        int x = i;
        for(;x;x -= lowbit(x))++ c[tot];
    }
    return ;
}
ull gcd(ull x,ull y) {
    return !y ? x : gcd(y , x % y);
}
int main() {
    freopen("examtwo.in","r",stdin);
    freopen("examtwo.out","w",stdout);
    scanf("%d%d%d",&n,&m,&k);
    if(n < m)swap(n , m);
    SIT = (1 << m) - 1;
    pre_solve();
    f[0][0][1] = 1;
    for(int i = 1;i <= n;++ i) {
        for(int j = 1;j <= tot;++ j) {
            for(int q = c[j];q <= k;++ q) {
                for(int p = 1;p <= tot;++ p) {
                    if(state[p] & state[j])continue ;
                    if(c[j] + c[p] > q)continue ;
                    f[i & 1][q][j] += f[1 - i & 1][q - c[j]][p];
                }
            }
        }
        memset(f[1 - i & 1] , 0 , sizeof(f[1 - i & 1]));
    }
    ull ans = 0;
    for(int j = 1;j <= tot;++ j)ans += f[n & 1][k][j];
    ull cnt = calc(k , n * m);
    ull t = gcd(ans , cnt);
    printf("%llu/%llu",cnt / t,ans / t);
    fclose(stdin);
    fclose(stdout);
    return 0;
}