题解

问题转化

将棋盘建模为二分图：

• 左部 $n$ 个顶点对应 $n$ 行（记作 $L_1,\ldots,L_n$）
• 右部 $n$ 个顶点对应 $n$ 列（记作 $R_1,\ldots,R_n$）
• 每个按钮位于 $(r_i,c_i)$ 对应一条边 $L_{r_i}-R_{c_i}$

设 $x_e \in \{0,1\}$ 表示边 $e$ 是否被选中（1 为激活），则：

• 第 $i$ 行激活按钮数 $R_i = \sum_{e \text{ 与 }L_i\text{ 关联}} x_e$
• 第 $j$ 列激活按钮数 $C_j = \sum_{e \text{ 与 }R_j\text{ 关联}} x_e$

条件要求所有 $R_i \bmod 2$ 相等，所有 $C_j \bmod 2$ 相等，且这两个相等值相同（设均为 $p \in \{0,1\}$）。

---

奇偶性分析

记 $d_i$ 为左部点 $i$ 的度数（该行的按钮总数），$d'_j$ 为右部点 $j$ 的度数（该列的按钮总数）。
在 $\mathbb{F}_2$（模 2 域）下，条件转化为：

$$\sum_{e \in \delta(L_i)} x_e \equiv p \quad (\forall i),\qquad \sum_{e \in \delta(R_j)} x_e \equiv p \quad (\forall j) $$

其中 $\delta(v)$ 表示与 $v$ 关联的边集。

这是一个包含 $2n$ 个方程、$m$ 个变量的模 2 线性方程组。

---

方程组的可解性

所有左方程相加：$\sum_{i=1}^n \sum_{e \in \delta(L_i)} x_e \equiv n p \pmod 2$
所有右方程相加：$\sum_{j=1}^n \sum_{e \in \delta(R_j)} x_e \equiv n p \pmod 2$
这两个和都等于 $\sum_{e} 2x_e \equiv 0 \pmod 2$，因此得到 $n p \equiv 0 \pmod 2$。

• 若 $n$ 为奇数，则 $p \equiv 0$，即 $p$ 必须为 0（全偶数）
• 若 $n$ 为偶数，则 $p$ 可为 0 或 1

所以 $n$ 的奇偶性决定了 $p$ 的可能取值。

---

构造方法

对每个可能的 $p$（0 或 1，由 $n$ 奇偶性决定是否都需尝试），在二分图上求解模 2 方程组。

算法步骤：

1. 建立二分图 $G=(L,R,E)$，边权 $x_e$ 为未知数。
2. 加入 $2n$ 个方程：
   $\deg_{L_i}(x) \equiv p$，$\deg_{R_j}(x) \equiv p$。
3. 注意到这些方程是线性相关的：所有左方程之和与所有右方程之和模 2 相等。
   去掉一个冗余方程（例如最后一个右方程），剩下 $2n-1$ 个独立方程。
4. 在 $\mathbb{F}_2$ 上高斯消元？$m$ 可达 $5\times 10^5$，不能直接消元。

巧妙构造：
将问题转化为在图中找一组边，使得每个顶点的度数奇偶性为 $p$。
这是经典问题：在任意无向图中，给定每个顶点的目标奇偶性，判断是否存在边子集满足要求。

构造算法（DFS 法）：

• 从任意顶点开始 DFS。
• 当回溯到顶点 $v$ 时，考虑其所有未被处理的邻边。
• 对每条边 $e=(u,v)$，递归处理 $u$。
• 回溯时，检查 $v$ 当前已决定的关联边中 $x_e=1$ 的个数奇偶性是否等于目标奇偶性 $p$。若不等，则选择边 $(v,parent(v))$（DFS 树边）使其翻转奇偶性。
• 最终每条边都被决定为 0 或 1。

这样可以在 $O(n+m)$ 时间内得到一组解（如果存在）。

---

非空解的处理

上述构造可能得到全 0 解（所有 $x_e=0$），但题目要求至少激活一个按钮。
若得到全 0 解：

• 如果 $p=1$：全 0 解不合法（奇偶性不满足），直接尝试另一种 $p$ 或判断无解。
• 如果 $p=0$：全 0 解符合奇偶性但按钮数为 0，需要调整。

调整方法：
若得到全 0 解，则任选一条边 $e$，将其设为 1。这会翻转其两个端点的度数奇偶性（从 0 到 1）。
在 $n$ 为偶数时，可以再选一条与 $e$ 无公共顶点的边 $f$ 设为 1，使所有顶点奇偶性回到 0。
若找不到两条不相邻的边，则需检查是否存在非全 0 解：这等价于判断边集是否包含一个非空偶子图（所有顶点度数为偶数的子图），即是否存在偶环。

---

无解判断

如果对所有可能的 $p$，上述构造都无法得到非空解，则输出 NIE。

---

时间复杂度

• 建图：$O(n+m)$
• DFS 构造解：$O(n+m)$
• 检查非空解与调整：$O(n+m)$
• 总复杂度：$O(n+m)$，适合 $n\le 10^5, m\le 5\times 10^5$。

---

关键点总结

1. 二分图建模与模 2 方程组：将行列奇偶性约束转化为顶点度数奇偶性约束。
2. $n$ 的奇偶性决定 $p$ 的可能取值：$n$ 奇则 $p=0$，$n$ 偶则 $p\in\{0,1\}$。
3. DFS 回溯构造：在线性时间内求解模 2 方程组，避免高斯消元。
4. 非空解保证：通过偶环检测或简单调整避免全 0 解。
5. 子任务引导：子任务 2 和 3 分别要求 $p=0$ 或 $p=1$ 的解，提示了分情况构造的思路。