この問題は、それぞれの bit ごとに操作が独立であるため、分けて考えることが出来ます。なので、\(0 \le A_{i,j} \le 1,-1 \le B_{i,j} \le 1\) である場合を考えます。もし、この場合が解ければ \(A,B\) の全ての bit に対して解くことで元の制約でも解くことが出来ます。

まず、操作を行うときにある行、列に何回も操作を行う必要はありません。その操作で選んだ全ての \(X\) の \(\mathrm{XOR}\) を \(X\) として操作を \(1\) 回行えばよいからです。

また \(X=0\) として操作を行う必要はないので、この問題は以下のように言い換えられます。

• 各行、列に \(1\) を \(\mathrm{XOR}\) するかしないかを選ぶことが出来る。 \(B_{i,j} \neq -1\) である \((i,j)\) に対して \(A_{i,j} = B_{i,j}\) と出来るか判定せよ。

ここで、\(0,1\) からなる長さ \(H,W\) の列 \(X=(X_1,X_2,\dots,X_H),Y=(Y_1,Y_2,\dots,Y_W)\) を \(X_i(1 \le i \le H) =「 i\) 行目に \(1\) を \(\mathrm{XOR}\) するかどうか(なるならば \(1\)、ならないならば \(0\))」 、\(Y_j(1 \le j \le W) =「 j\) 列目に \(1\) を \(\mathrm{XOR}\) するか(なるならば \(1\)、ならないならば \(0\))」と定義します。

すると、\(B_{i,j} \neq -1\) である全ての \((i,j)\) に対して、\(X_i\ \mathrm{XOR}\ Y_j\) を \(A_{i,j}\ \mathrm{XOR}\ B_{i,j}\)にせよ。という問題になります。

まず、\(X_1 = 0\) としてよいです。もし、\(X_1 = 1\) であり条件を満たす \((X,Y)\) が存在したら、\(X'_i=1-X_i,Y'_j=1-Y_j\) となるような \((X',Y')\) も条件を満たし、\(X'_1=0\) となるからです。

次に、\(B_{1,j} \neq -1\) であるような \(j\) に対して \(Y_j\) が決まります。さらに、\(B_{i,j} \neq -1\) であるような \(i\) に対して \(X_i\) が決まります。さらに、…… のようにこの手続きを繰り返していけばよいです。もしこの手続き中に矛盾が生じる。つまり既に \(Y_j\) が決まっているのに \(X_i\ \mathrm{XOR}\ Y_j \neq\) \(A_{i,j}\ \mathrm{XOR}\ B_{i,j}\) となったならば条件を満たす \((X,Y)\) は存在しません。

また、この手続きで決まらない \(X_i\) もしくは \(Y_j\) があれば、\(X_i=0\)、もしくは \(Y_j=0\) として上記の手続きを繰り返すことを繰り返せばよいです。

このアルゴリズムは、グラフの言葉に置き換えると以下のようになります。

二部グラフ \(G\) が与えられる。\(G\) の辺全てに対して \(0\) か \(1\) のパラメーターがついている。全ての頂点に \(0\) か \(1\) を割り当てる方法のうち、全ての辺に対して「辺のパラメーター \(=\) 辺が結ぶ頂点に割り当てられた頂点の \(\mathrm{XOR}\)」となるようなものは存在するか？

上記の解法はグラフ上である頂点に \(0\) を割り当て、bfs で同じ連結成分にある頂点の整数の割り当てを定め、もし矛盾が生じれば不可能とする。と解釈できます。

計算量は \(\mathrm{O}(HW)\) を \(\log A\) 回行うため \(\mathrm{O}(HW\log A)\) です。