Codeforces 461(#263 Div1) D. Appleman and Complicated Task

Codeforces 線形代数

問題

nxnのグリッドの各マスに'o'か'x'を、次の条件を満たすように入れる。

  • 各マスについて、隣接する４マスのうち、'o'が書かれたマスは偶数個

nxnのうち、k個のマスに入るものがあらかじめ決まっているとき、
残りのマスの埋め方は何通りあるかmod 10^9 + 7で求めよ。

制約条件

n≦10^5
k≦10^5

方針

Editorial見た。
グリッドの状態は、最初の一行を決めればユニークに決まり、
一般的にはa[i][j] = Xor{a[0][k] | k≦i+j≦2(n-1)-k かつ |i-j|≦k かつ k%2=(i+j)%2}
と書けるらしい。
（これはどうやったら発見できるんだろう）


なので、i+jを偶数と奇数の場合にわけると、
a[i][j]に関係するkは、L≦k≦Rであり、a[i][j] = a[0][L] ^ a[0][L+1] ... ^ a[0][R]と書けることになる。


この等式を表現するのはunion-findを使えばよい。
s[x] = Xor{a[0][k] | k＜x}とすれば、a[i][j] = 0⇔s[R + 1] = s[L]
蟻本の食物連鎖の問題にある感じで、s[x] = 0, 1に対応する頂点をそれぞれ作って、
s[x] = aとs[y] = bが同時に起こるときにs[x] = aの頂点とs[y] = bの頂点をunionする。


で、等式を全部unionし終えた後、s[x] = 0とs[x] = 1の頂点が同じunionにあったら答えは0.
そうでなかったら、答えは2^(unionの個数/2 - 1)通り。

ソースコード

const int MX = 220000;
int odd[MX], even[MX];
int root(int *p, int x){
	if(x == p[x]) return x;
	return p[x] = root(p, p[x]);
}
bool merge(int *p, int a, int b){
	a = root(p, a); b = root(p, b);
	if(a == b) return 0;
	p[b] = a;
	return 1;
}

int n, q;

int main(){
	scanf("%d%d", &n, &q);
	rep(i, 2 * n + 2){
		odd[i] = i;
		even[i] = i;
	}
	int cmp = n;
	while(q--){
		int x, y; char c;
		scanf("%d%d %c", &y, &x, &c);
		x--; y--;
		
		int L = abs(x - y);
		int R = min(x + y, 2 * (n - 1) - x - y);
		
		int *target = (x + y) % 2 ? odd : even;
		int res = 0;
		
		if(R % 2 != (x + y) % 2) R--;
		L /= 2; R /= 2;
		R++;
		
		if(c == 'o'){
			res |= merge(target, 2 * L, 2 * R + 1);
			res |= merge(target, 2 * L + 1, 2 * R);
		}
		else{
			res |= merge(target, 2 * L, 2 * R);
			res |= merge(target, 2 * L + 1, 2 * R + 1);
		}
		cmp -= res;
	}
	ll ans = 1;
	rep(i, cmp) ans *= 2, ans %= inf + 7;
	rep(i, n){
		if(root(odd, 2 * i) == root(odd, 2 * i + 1)) ans = 0;
		if(root(even, 2 * i) == root(even, 2 * i + 1)) ans = 0;
	}
	cout << ans << endl;
	return 0;
}