会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
解题思路
把「颜色」直接看成一个 n 位二进制掩码：第 i 位为 1 表示第 i+1 个彩球是黄色，为 0 表示红色。最终目标就是让掩码变成全 0。
一次触碰做了什么。 触碰第 i 个彩球，会翻转它自己；如果还有关系 [i, v]，则第 v 个彩球也一起翻转。翻转就是异或 1，所以可以预处理出每个彩球的「影响掩码」：effect[i] = (1 << i) | (1 << (v-1))，其中 v 取遍所有满足 edges[j] = [i, v] 的关系。
触碰顺序无关。 每个彩球被触碰偶数次等于没碰，被触碰奇数次等于碰一次；因此最优方案中每个彩球最多碰一次。设方案是一个 n 位 0/1 向量 x，则「所有彩球都变红」等价于：把所有满足 xi=1 的 effect[i] 异或起来，结果恰好等于初始颜色掩码 target（黄色为 1）。于是问题变成：在 GF(2) 上解线性方程组，并在所有解中找 1 的个数最少 的向量；次数相同时，再找对应编号列表字典序最小的。
为什么不能直接枚举 2n。 n≤23 时 223=8388608，C++ 尚可，但 Python、JavaScript 在 1 秒时限下很危险。用 折半枚举（meet in the middle） 可以把指数减半。
