問題

https://codeforces.com/problemset/problem/1391/D

$n$ 行 $m$ 列の01行列 $a$ において、全ての部分偶数長正方行列に含まれる1の数を奇数にするための最小操作回数を求めよ。

解法

$n \leq m$ とする（そうでない場合は $a$ を転置）。

$n = 1$ の場合、部分偶数長正方行列は存在しないため $0$ 。

$n = 2$ の場合、 $a_{00} + a_{10}$ の偶奇を決めてしまえば後の列の偶奇は自然に定まるため、2通り試す。
偶奇の状態は、00 or 11、01 or 11であり、どの調整も1回の操作で済む。

$n = 3$ の場合、 $a_{00} + a_{10}$ と $a_{10} + a_{20}$ の偶奇を決めてしまえば後の列の偶奇は自然に定まるため、4通り試す。
偶奇の状態は、000 or 111、001 or 110、010 or 101、011 or 100であり、どの調整も1回の操作で済む。