盤面の外周が黒マスで覆われていると考える

一旦，すべてのこだわりを満たすことができるか，という問題を考える．

自身は白だが，一個上のマスは黒というマスをタイプVと呼ぶことにする． 自身は白だが，一個左のマスは黒というマスをタイプHと呼ぶことにする． タイプVかつHということはあり得る．

自身は白で，タイプVでもHでもないが，一個左上のマスが黒というマスをタイプQと呼ぶことにする．

タイプV,H,Qのマスの値を全部決めると，盤面全体が自動的に決まる． また，タイプV,H,Qのマスの値の決め方は完全に自由である

ところで，次のような手順で任意のよい盤面を生成できる

• 各タイプVのマスについて，そのマスから下に進んでいき，初めて黒と出会うまでの区間を考える． この区間全体に (\(0\) or \(1\)) を XOR する．
• 各タイプHのマスについて，そのマスから右に進んでいき，初めて黒と出会うまでの区間を考える． この区間全体に (\(0\) or \(1\)) を XOR する．
• 各タイプQのマスについて，そのマスの右下(同じ行/列含む)にあるすべてのマスに(\(0\) or \(1\)) を XOR する．ここでは到達可能性などは一切考慮せず，単に座標だけ見て右下領域に一様に XOR する．

この手順で任意のよい盤面が生成できることは簡単にわかる （V,H,Qのマスを左上から見ていって，目標状態に向かって適宜操作を行うと考えれば良い）

任意のマス \((i,j)\) について，それに影響する操作を考えると，

• \((i,j)\) から上に進んだ突き当りにあるマスでのV操作
• \((i,j)\) から左に進んだ突き当りにあるマスでのH操作
• \((i,j)\) より左上にあるマスでのQ操作

である． 各操作で使用した値 (\(0\) or \(1\)) を変数とすれば，各こだわりは mod \(2\) での一次方程式になる． しかし変数の数が多いので困る．

V,H に対応する変数の数が多いが，各方程式では V,H 変数は \(1\) つずつだけ登場する． そこで，V,H 変数の制約はグラフで表現することにする． V,H マスに対応する頂点を作り，各こだわりでは対応する頂点間の辺を張る． 辺の重みとしては，Q変数の01列を持つことにする． グラフ上でサイクルができたら，そのサイクル内でのQ変数のXORをとり，ここで得た方程式を条件として追加していく．

これはincrementalにやることも可能である． ポテンシャル付きunion-findのポテンシャルをbit列にして，サイクルが出てくるたびにそこからQ変数の方程式を得て，それが充足可能か計算すればよい．

連立方程式を解くときは普通のガウス法をbitsetで高速化してやるとよい．

計算量は全体で \(O(MN+MN \log(M)/W + MN^2/W)\) (ただし \(W\) は word size)

回答例(C++)