Codeforces #1014 : Div2 E. She knows...

ちょっと手間取った。
https://codeforces.com/contest/2092/problem/E

問題

H*Wのグリッドがあり、これを白黒に塗り分けることを考える。
うち、Kマスの色はすでに与えられている。

この時、Aを、隣接マスの対のうち色が異なるものの個数とする。
Aが偶数となるような塗り分けは何通りあるか。

解法

角を除く外周部のみ、Aの偶奇に関係する。
それ以外のマスは2又は4マス隣接マスがあるため、そのマスを白黒どちらに塗ったとしてもAの偶奇は変わらないためである。

そこで指定された箇所のうち外周部のセルの数を数える。
もし外周部に残りがある場合、残った1セルの色を決めると残りも全部決まるので解は2^(H*W-K-1)通り。
外周部がすべて指定されているとき、黒の数が奇数だと解は0。そうでない場合、他のマスはすべてどうとでもできるので2^(H*W-K)通り。

int T;
ll H,W,K;
const ll mo=1000000007;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>H>>W>>K;
		ll a=2*((H-2)+(W-2));
		int C[2]={};
		FOR(i,K) {
			cin>>y>>x>>k;
			if((y==1||y==H)&&(x!=1&&x!=W)) {
				a--;
				C[k]++;
			}
			if((x==1||x==W)&&(y!=1&&y!=H)) {
				a--;
				C[k]++;
			}
		}
		
		ll ret=0;
		if(a) {
			ret=modpow(2,H*W-K-1);
		}
		else {
			ret=modpow(2,H*W-K);
			if(C[0]%2) ret=0;
		}
		cout<<ret<<endl;
		
	}
}

まとめ

結果的に出てくる数式はシンプル。