CF1391D 505

如果一个二进制矩阵的每一个偶数边长的正方形子矩阵中 $1$ 的个数都是奇数，则称该矩阵是“好”的。 给定一个由 $n$ 行 $m$ 列组成的二进制矩阵 $a$，请你求出最少需要修改多少个单元格，才能使其变为“好”的矩阵。如果无法做到，请输出 $-1$。 上述所有术语的正式定义请参考提示部分。

输入的第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq m \leq 10^6$ 且 $n\cdot m \leq 10^6$），分别表示矩阵 $a$ 的行数和列数。 接下来的 $n$ 行，每行包含 $m$ 个字符，每个字符为 $0$ 或 $1$。如果第 $i$ 行第 $j$ 个字符为 $1$，则 $a_{i,j}=1$；如果为 $0$，则 $a_{i,j}=0$。

输出最少需要修改多少个单元格，才能使 $a$ 变为“好”的矩阵。如果无法做到，输出 $-1$。

在第一个样例中，将 $a_{1,1}$ 改为 $0$，$a_{2,2}$ 改为 $1$ 即可满足条件。 你可以验证第二个样例无法通过任何方式使矩阵变为“好”的。 一些定义说明： - 二进制矩阵指的是每个元素都是 $0$ 或 $1$ 的矩阵。 - 子矩阵由 $4$ 个参数描述——$r_1$、$r_2$、$c_1$ 和 $c_2$，其中 $1 \leq r_1 \leq r_2 \leq n$，$1 \leq c_1 \leq c_2 \leq m$。 - 该子矩阵包含所有满足 $r_1 \leq i \leq r_2$ 且 $c_1 \leq j \leq c_2$ 的元素 $a_{i,j}$。 - 如果 $r_2-r_1 = c_2-c_1$ 且 $r_2-r_1+1$ 能被 $2$ 整除，则该子矩阵称为偶数边长的正方形子矩阵。 由 ChatGPT 4.1 翻译