题目大意

我们有一个$n \times m$的 01 矩阵。

• 定义 $r$ 为行异或值为 1 的行数（即该行所有元素按位异或结果为 1）。
• 定义 $c$ 为列异或值为 1 的列数（即该列所有元素按位异或结果为 1）。

一次操作：选择矩阵中的一个元素，将它 翻转（0 变 1，1 变 0）。

目标是让 $r = 0$ 且$c = 0$，即所有行异或和都为 0，所有列异或和都为 0。

问最少操作次数是多少。

---

关键观察

设矩阵元素为 $a_{ij} \in \{0,1\}$。

第 $i$ 行的异或和：

$$R_i = a_{i1} \oplus a_{i2} \oplus \dots \oplus a_{im} $$

第 $j$ 列的异或和：

$$C_j = a_{1j} \oplus a_{2j} \oplus \dots \oplus a_{nj} $$

根据标程的思路，当我们翻转元素$a_{ij}$：

• 这一行的异或值会翻转（因为 $R_i$ 变为 $R_i \oplus 1$）。
• 这一列的异或值也会翻转（因为 $C_j$ 变为 $C_j \oplus 1$）。

因此，一次操作会同时改变：

• 某一行在行异或为 1 的行数 $r$ 的变化量是 ±1
• 某一列在列异或为 1 的列数 $c$ 的变化量是 ±1

也就是说，一次操作会同时让 $r$ 和$c$ 各自变化 $\pm 1$。

---

重要性质

由异或的性质可知：

1. 所有行异或和的总异或值（对 $R_i$ 再异或一次）等于 所有列异或和的总异或值。
2. 其实更直接：
   矩阵所有元素的总异或值 = 各行的异或值再异或
   矩阵所有元素的总异或值 = 各列的异或值再异或

由此可得一个重要结论：

$$\text{（行异或值为 1 的行数）} \bmod 2 = \text{（列异或值为 1 的列数）} \bmod 2 $$

因为：

• 所有行异或值的异或 = 矩阵所有元素的总异或
• 所有列异或值的异或 = 矩阵所有元素的总异或
• 所以行异或值和列异或值的奇偶性相等。

即

$$r \bmod 2 = c \bmod 2$$

这个结论与题解给出的“不可能情况”无关（因为题中没给不可能情况），而是用于辅助推导最小操作次数。

---

最少操作次数推导

设初始时 $r$ 和 $c$ 如上定义。
我们需要最终$r=0, c=0$。

一次操作使 $r$ 和 $c$各自变化 1（增加或减少），所以变化量记为 $ (\Delta r, \Delta c) \in \{(-1,-1), (-1,1), (1,-1), (1,1)\} $，取决于翻转的元素是否在原来行异或为 1 的行和列异或为 1 的列中。

目标是让$r \to 0, c \to 0$。

一种贪心策略：

• 如果 $r > c$，那么我们可以每次选择在某个行异或为 1 的行，列异或为 0 的列（即该行列异或状态不同）上操作，这样会使 $r$ 减少 1，$c$ 增加 1，直到 $r = c$。
• 当 $r = c$ 时，如果 $r = c = k$，一次操作可以同时减少 $r$和 $c$ 各 1，所以还需要 $k$ 次。
• 如果初始 $r < c$，同理先通过操作把 $c$ 拉到 $r$，再同步减少。

总次数：

$$\text{答案} = \max(r, c)$$

因为：

1. 每次只能减少 $\min(r,c)$ 中的一个，或者同时减少两者。
2. 最少的次数就是先减少较大的那个，直到相等，再同步减少。

---

正确性说明

假设$r \ge c$，我们先选一个行异或为 1 的行的某个列异或为 0 的列（一定存在吗？不一定总存在，但我们可以构造策略，或者通过全异或相等条件确保能到终点）。

实际上，我们可以考虑更简单的数学归纳：

• 当 $r = 0, c = 0$ 时，次数为 0。
• 当 $r \ge c > 0$ 时，可以一步让 $r$ 减少 1 且$c$ 增加 1（如果可行），这样 $r-c$ 减少 2，直到 $r=c$。
• 当 $r=c>0$ 时，可以一步让 $r$ 和$c$ 都减 1。
• 所以需要的步数正好是$\max(r,c)$。

---

时间复杂度

计算 $r$ 和 $c$：

• 对每行做异或和：$O(nm)$
• 对每列做异或和：$O(nm)$

总复杂度 $O(nm)$，符合题意。

---

与标程对照

标程中：

• 先读入矩阵，存为 bool
• 分别计算 $r$ 和 $c$
• 输出 $\max(r,c)$

没有特殊处理，因为题目保证有解（即满足奇偶性条件），所以直接输出 $\max$即可。

---

最终题解公式化

$$\text{答案} = \max(r, c)$$

其中

$$r = \sum_{i=1}^n \left( \bigoplus_{j=1}^m a_{ij} \right) $$$$c = \sum_{j=1}^m \left( \bigoplus_{i=1}^n a_{ij} \right) $$

这里 $\oplus$ 表示按位异或，求和是把 true 值当 1 计数。

---