定义
- 必胜或必胜状态：仅仅考虑当前的状态，不考虑的操作人时，一定必胜或必输
- \(a\oplus b\) ：\(a,b\) 在二进制下，对位取反。
Nim 游戏
考虑有 \(n\) 堆石子，两个人轮流来拿走棋子（至少拿一个），拿到最后剩下的一颗棋子的人获胜。
结论：
定义 Nim 和 \(= a_1\oplus a_2\oplus a_3\oplus\dots\oplus a_n\)。
当 Nim 和 为 \(0\) 时，该状态为必败状态；反之，则为必胜状态。
证明：
我们需要三个引理：
-
无后继状态为必败状态
这个情况只有全 \(0\)，同时满足 \(a_1\oplus a_2\oplus\dots\oplus a_n=0\) 。
-
对于当前状态 \(a_1\oplus a_2\oplus\dots\oplus a_n\ne0\)，一定存在某种移动使得其异或和为 \(0\)
考虑来构造一下：
设 \(a_1\oplus a_2\oplus\dots\oplus a_n=s\)，同时设 \(s\) 的在二进制下，最高位为 \(k\) 。
如果我们想使 \(s\) 变为 \(0\)，就非常想两边同时乘 \(s\) 。
但是每次进行一次拿石子必须需要时某个 \(a_i\) 减少，
所以可以考虑在 \(a_i\) 处拿，则需要证明 \(a_i\oplus s<a_i\) 的。
现在来想一想异或的定义，发现 \(s\) 最高位为 \(1\) ，则在 \(a_1,a_2\dots,a_n\) 肯定有一个 \(t\) ，使得 \(a_t\) 这一位也是 \(1\)
那就拿 \(a_t\oplus s\) ，我们又发现最高位变成了 \(0\) 。
由于这是最高位，则 \(a_t\) 比 \(k\) 还高的位就不会改变，所以 \(a_t\oplus s\) 一定 \(<a_t\) 。
于是就构造出来一组解了。
-
对于当前状态 \(a_1\oplus a_2\oplus\dots\oplus a_n=0\)，一定不存在某种移动使得其异或和为 \(0\)
也就是说，只要有一个 \(a\) 数组中数的位发生改变，那么其异或和就不为零了。