1 条题解
-
0
容斥好题。
题目条件有行列和对角线，不是很好处理。
考虑如果暴力容斥，直接枚举让那些行、列、对角线变成全是列，时间复杂度为 直接爆炸。
考虑将总概率减去每一行列对角线都有至少一个 的概率。
枚举选取列和对角线的情况，这样我们就可以知道一些位置必须要选 。
那么由于一定不能有一行满足全是 ，所以剩下的地方只要不是一行全都是 就可以了。
设 表示在第 行选取的列的集合为 的概率，预处理时间复杂度 。
枚举列与对角线的状态之后，设 表示前 行当前选取集合为 的列的概率。
$$f_{i,S}=f_{i-1,S}\times s_{i,SS}\times (1-s_{i,U\oplus SS}) $$其中 表示算上对角线后，当前这一行必须天填 的代价， 表示全集。
代码
#include<bits/stdc++.h> using namespace std; const int N=21,maxS=(1<<N)+5,mod=31607; int n,a[N+5][N+5],lg2[maxS],cnt[maxS],f[maxS],sum[N+5][maxS],ans; int kuai(int a,int b){//快速幂 int ans=1; for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)ans=1ll*ans*a%mod; return ans; } int main(){ scanf("%d",&n); int Inv=kuai(10000,mod-2); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&a[i][j]),a[i][j]=1ll*Inv*a[i][j]%mod; for(int i=0;i<n;i++)lg2[1<<i]=i+1; for(int i=0;i<1<<n;i++)cnt[i]=cnt[i>>1]+(i&1);//预处理二进制中1的数量 for(int i=1;i<=n;i++){ sum[i][0]=1; for(int S=1;S<1<<n;S++){ int x=S&-S; sum[i][S]=1ll*sum[i][S^x]*a[i][lg2[x]]%mod; } } for(int T=0;T<4;T++){ for(int S=0;S<1<<n;S++)if((cnt[S]+cnt[T])&1)f[S]=mod-1;//容斥系数 else f[S]=1; for(int i=1;i<=n;i++){ for(int S=0;S<1<<n;S++){ int SS=S; if(T&1)SS|=(1<<(i-1)); if(T&2)SS|=(1<<(n-i)); f[S]=1ll*f[S]*sum[i][SS]%mod*(1-sum[i][((1<<n)-1)^SS]+mod)%mod; } } for(int S=0;S<1<<n;S++)ans=(ans+f[S])%mod; } printf("%d",(1-ans+mod)%mod); }
- 1