あまり出来の良くなかった回。
https://codeforces.com/contest/1530/problem/F
問題
N*Nのグリッドがあり、各セルが黒くなる確率が与えられる。
縦・横・斜めのいずれかに、黒セルが並んだ列が1つ以上できる確率を求めよ。
解法
黒列が1つもできない確率を求めよう。
f(r,mask) := 上からr行目までの白黒を考えたとき、r行目までで黒セルが並んだ行が1個もなく、列または斜め方向で黒列が生成される可能性がmaskで示されるような状態に至る確率
f(r,mask)→f(r+1,mask')の遷移を考えよう。
まず1行分の白黒のパターンmask''を列挙したうえで、包除原理と高速ゼータ変換で(mask & mask'')=mask'となるようなf(r,mask)とmask''を構成する確率の積和を求められる。
int N; int A[21]; const int mo=31607; int modpow(int a, int n = mo-2) { int r=1;a%=mo; while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1; return r; } int C[1<<23]; int from[1<<23]; ll fal; int md,ad; void dfs(int cur,int v,int mask) { if(cur==N) { C[mask]=v; } else { dfs(cur+1,v*(1-A[cur]+mo)%mo,mask); dfs(cur+1,v*A[cur]%mo,mask|(1<<cur)); } } void solve() { int i,j,k,l,r,x,y; string s; int mask; cin>>N; ll p=1; FOR(i,(1<<(N+2))) from[i]=1; FOR(y,N) { FOR(x,N) { cin>>k; A[x]=k*modpow(10000)%mo; } ZERO(C); md=y; ad=N-1-y; dfs(0,1,0); fal+=p*C[(1<<(N))-1]; p=p*(1-C[(1<<(N))-1]+mo)%mo; C[(1<<(N))-1]=0; FOR(i,N) { FOR(mask,1<<(N)) if(mask&(1<<i)) { (C[mask^(1<<i)]+=C[mask]); if(C[mask^(1<<i)]>=mo) C[mask^(1<<i)]-=mo; } } FOR(mask,1<<(N+2)) { int mask2=mask&((1<<N)-1); if(mask&(1<<N)) mask2|=1<<md; if(mask&(1<<(N+1))) mask2|=1<<ad; from[mask]=C[mask2]*from[mask]%mo; } fal%=mo; } FOR(i,N+2) { FOR(mask,1<<(N+2)) if(mask&(1<<i)) { from[mask^(1<<i)]-=from[mask]; if(from[mask^(1<<i)]<0) from[mask^(1<<i)]+=mo; } } ll ret=fal%mo; FOR(mask,1<<(N+2)) if(mask) ret+=from[mask]; cout<<ret%mo<<endl; }
まとめ
包除原理を繰り返す問題、頭が混乱しがち。