比赛 |
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;
}