问题分析

1.操作的性质 设一个开关连接灯泡 $a$ 和 $b$。

如果 $s_a = s_b$，那么按下开关后：

若 $s_a = s_b = 0$，则变为 $1,1$

若 $s_a = s_b = 1$，则变为 $0,0$

如果 $s_a \neq s_b$，那么操作无效。

这个条件看起来比经典的“开关翻转连接的灯泡”要复杂，因为操作依赖于当前状态。

2.关键转化 我们定义一个新的状态表示： 设 $x_i \in {0,1}$ 表示灯泡 $i$ 的目标状态与初始状态是否不同（即是否需要翻转）。 初始时所有 $x_i = 0$。

考虑一个开关 $(u,v)$ 在什么条件下能改变状态：

在原问题中，开关 $(u,v)$ 有效的条件是 $s_u = s_v$。 在翻转表示下，$s_u' = s_u \oplus x_u$，$s_v' = s_v \oplus x_v$。

开关操作的效果是：如果 $s_u' = s_v'$，那么可以同时翻转 $x_u$ 和 $x_v$（即 $x_u \leftarrow x_u \oplus 1$，$x_v \leftarrow x_v \oplus 1$）。

图论建模

建立图 $G$：

顶点：$n$ 个灯泡

边：每个开关 $(u,v)$ 是一条边，权值为 $w = s_u \oplus s_v$

方程 $x_u \oplus x_v = w$ 是图上的异或约束。

求解方法

对每个连通分量：

任选一个顶点 $r$，设 $x_r = 0$（或其他值）

通过 DFS/BFS 确定其他顶点的 $x_i$ 值

如果出现矛盾（同一个顶点被赋予两个不同的值），则该连通分量无解 → 整个系统无解？等等，这里要小心

实际上，这个方程组总是有解的，因为我们可以选择 $x_r = t$（$t \in {0,1}$），然后推导出其他变量。 每个连通分量会产生 $2$ 种可能的 $(x_1,\dots,x_n)$ 赋值方案吗？

仔细分析：

对于连通分量，一旦确定某个顶点的值，其他顶点值唯一确定。 所以每个连通分量有 $2$ 种可能的赋值（对应选择 $x_r=0$ 或 $x_r=1$）。

但是这些赋值不一定都对应有效的状态翻转吗？ 在本题中，所有赋值都是有效的，因为方程 $x_u \oplus x_v = w$ 就是根据开关操作的可执行条件推导出来的，满足方程就意味着操作可以执行。

自由度和答案

设图有 $k$ 个连通分量。 每个连通分量的 $x$ 变量有 $2$ 种取值方案，所以总方案数 = $2^k$。

但是注意：$x$ 变量的每种取值对应唯一的目标状态（目标状态 = 初始状态 ⊕ $x$），所以可达状态数 = $2^k$。

特别地，初始状态本身对应 $x=0$，包含在 $2^k$ 中。