No.460

手順は XOR を積み重ねるものなのでマスの指定順序は関係なく, また同じマスを2回指定することは意味がない.

$(i,j)$ のマスを指定するかどうかを $b_{i, j}$ とする.

まず, $1$ 行目/$1$列目を決める.

そうすると, $a_{1,1}$ は残り $b_{2,2}$ にしか影響を受けないので, $b_{2,2} = a_{1,1}$ となる. 以下芋づる式に $b_{2,3}, b_{2,4}, \dots$ と決まる. すべて決めたときに $M$行目/$N$ 列目がすべて $0$ になっていなければ矛盾なので最初に決めた $1$ 行目/$1$ 列目が間違っている.

$1$行目/$1$列目のすべてのパターンでこれを試す.