kmjp's blog

競技プログラミング参加記です

Codeforces #733 : F. Bingo

あまり出来の良くなかった回。
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;
	
}

まとめ

包除原理を繰り返す問題、頭が混乱しがち。