CF1530F
题解
- 容斥
- 问至少 1 行/列/对角线 全为 1 的概率
- 转化为求每 行/列/对角线 至少有 1 个 0 的概率
- 总概率 1 减去他就是答案
- 每行的状态相互独立
- 考虑枚举列和对角线的状态,0 表示存在 0,1 表示全是 1
- 根据列和对角线能推出每一行的状态
- 每一行的状态乘积就是当前 列/对角线 的状态的方案数
- 对于 列/对角线的状态
- 减去有奇数个 1 的,加上有偶数个 1 的
代码
# include <bits/stdc++.h>
# define int long long
using namespace std;
const int MOD = 31607;
const int N = (int)2e6 + 10;
int n, temp;
int f[22][1 << 21];
int ans;
int Q_pow(int a, int b){
int ans = 1, p = a;
while(b){
if(b & 1){
ans = (ans * p) % MOD;
}
p = (p * p) % MOD;
b >>= 1;
}
return ans;
}
int lowbit(int x){
return x & (-x);
}
signed main(){
cin >> n;
int up = (1 << n) - 1, base = Q_pow(10000ll, MOD - 2);
for(int i = 1; i <= n; i++){
f[i][0] = 1;
for(int j = 1; j <= n; j++){
cin >> temp;
temp = temp * base % MOD;
f[i][1 << (j - 1)] = temp;
}
for(int j = 1; j <= up; j++){
f[i][j] = f[i][j ^ lowbit(j)] * f[i][lowbit(j)] % MOD; // 状压这一行对应的列的状态
}
}
int upp = (1 << 2) - 1;
for(int i = 0; i <= upp; i++){
for(int j = 0; j <= up; j++){
int cnt = __builtin_popcount(i) + __builtin_popcount(j);
int num = 0; // 容斥系数
if(cnt % 2){
num = -1;
}else{
num = 1;
}
for(int k = 1; k <= n; k++){
int a = j; // 列的状态
int b = (i & 1) * (1 << (k - 1)); // 对角线 1 在 第 i 行对应的状态
int c = ((i >> 1) & 1) * (1 << (n - k)); // 对角线 2 在 第 i 行对应的状态
int d = a | b | c;
num = num * (f[k][d] - f[k][up] + MOD) % MOD;
}
ans = (ans + num) % MOD;
}
}
ans = (1 - ans + MOD) % MOD;
cout << ans << "\n";
}
标签:CF1530F,const,temp,状态,int,对角线
From: https://www.cnblogs.com/wangyangjena/p/18028340