一年一更任務達成√

題目鏈接：F - Bingo

題目大意：給定一個 \(n\times n(n\le 21)\) 表格，表格中每個元素有 \(p_{i,j}\) 的概率為 \(1\)，否則為 \(0\)。求至少有一行或一列或一條對角線全為 \(1\) 的概率，其中對角線指兩條主副對角線。

考慮一個 naive 的容斥想法，直接容斥有多少條（行/列/對角線）是不全為 \(1\) 的，并進行計算。

此時發現不全為 \(1\) 的計算很繁，于是考慮求原題的補集。即求所有（行/列/對角線）均不全為 \(1\)（或者說均存在 \(0\)）的概率，那么容斥之后則是求欽定某些（行/列/對角線）均全為 \(1\) 的概率，這個概率可以非常直接地算出來：把所有被欽定為 \(1\) 的位置對應的 \(p_{i,j}\) 乘起來即可。

那么采用這種做法，復雜度則是 \(O(n^22^{2n})\) 級別的，顯然無法接受。

考慮一個神奇的想法，把容斥計算拆成兩部分。假設我們已經欽定了有哪些列或對角線是全為 \(1\) 的，觀察下我們計算的是什么。

我們的式子本來是所有被欽定為 \(1\) 的位置的 \(p_{i,j}\) 之積，而現在在這一前提下，則變成我們要再次欽定有哪些行是全為 \(1\) 的，并計算 在第一輪欽定中變為 \(1\) 的 \(p_{i,j}\) 之積乘上（枚舉第二輪欽定哪些行全為 \(1\)，并計算容斥系數乘上在第二輪欽定中新成為 \(1\) 的 \(p_{i,j}\) 之積的和）。

而對于括號內的部分，對應式子的意義等同于求每一行均不全為 \(1\) 的概率。這時我們發現，這里的每一行相互之間是獨立的，所以每行的貢獻可以分開算，最后再乘起來就好。

于是我們考慮對每一行預處理在欽定了些列或對角線為 \(1\) 后，該行不全為 \(1\) 的概率。注意到欽定某些位置為一相當于修改對應的 \(p_{i,j}\) 使其變為 \(1\)。所以把對應行 \(p_{i,j}\) 的乘積直接除掉對應列集合的乘積即可，這玩意可以直接利用 lowbit 轉移 \(O(2^n)\) 求出來，而對于對角線的部分直接枚舉四種情況分別做就好。這樣時間復雜度是 \(O(n2^n)\) 的，足以通過此題。

在實現時，可以先 \(2^2\) 枚舉對角線的情況，再容斥列，這樣實現起來會方便些。

#include<bits/stdc++.h>
using namespace std;
#define MOD 31607
#define N 21
int n,m,ans,a[N][N],b[N][N],f[N][1<<N],c[N],g[1<<N],k[1<<N],Lg[1<<N];
int lowbit(int x){return x&(-x);}
int sol()
{
	int res=0;
	for(int i=0;i<n;i++){
		f[i][0]=1;
		for(int j=1;j<=m;j++)
			f[i][j]=f[i][j^lowbit(j)]*b[i][Lg[lowbit(j)]]%MOD;
		for(int j=0;j<=m;j++)f[i][j]=(MOD+1-f[i][j])%MOD;
	}
	for(int j=0;j<=m;j++)
		for(int i=n-2;i>=0;i--)
			(f[i][j]*=f[i+1][j])%=MOD;
	for(int i=0;i<=m;i++)
		res=(res+f[0][m^i]*g[i]%MOD*k[i])%MOD;
	return res;
}
int pre(int o1,int o2)
{
	int K=1;
	for(int i=0;i<n;i++)
	for(int j=0;j<n;j++)
		b[i][j]=a[i][j];
	if(o1)for(int i=0;i<n;i++)(K*=b[i][i])%=MOD,b[i][i]=1;
	if(o2)for(int i=0;i<n;i++)(K*=b[i][n-i-1])%=MOD,b[i][n-i-1]=1;
	for(int i=0;i<n;i++)c[i]=1;
	for(int i=0;i<n;i++)
	for(int j=0;j<n;j++)
		c[j]=c[j]*b[i][j]%MOD;
	g[0]=1;
	for(int i=1;i<=m;i++)
		g[i]=g[i^lowbit(i)]*c[Lg[lowbit(i)]]%MOD;
	return K*sol()%MOD;
}
int main()
{
	k[0]=1;
	for(int i=0,o=1;i<N;i++,o<<=1)Lg[o]=i;
	for(int i=1;i<(1<<N);i++)k[i]=MOD-k[i^lowbit(i)];
	scanf("%d",&n),m=(1<<n)-1;
	for(int i=0;i<n;i++)
	for(int j=0;j<n;j++){ 
		scanf("%d",&a[i][j]);
		(a[i][j]*=3973)%=MOD;
	}
	for(int i=0;i<2;i++)
	for(int j=0;j<2;j++)
		ans=(ans+(i^j?MOD-1:1)*pre(i,j))%MOD;
	printf("%d\n",(MOD+1-ans)%MOD);
}