nim 游戏

给出结论：将所有数异或，若结果为 \(0\)，先手必败，否则先手必胜。

设异或值为 \(x\)。

证明分三步：

全 \(0\) 局面先手必败。
对于当前局面若 \(x\neq0\)，存在某种方式将其变为 \(0\)：

考虑 \(x\) 的最高的为 \(1\) 二进制位（记为 \(k\)），原序列中肯定有至少一个（奇数个）数第 \(k\) 位为 \(1\)。（设为 \(a_i\)）所以 \(a_i\oplus x<a_i\)（前面的位保持不变，然后第 \(k\) 位变为 \(0\)，后面就算均增加也会减少）。那么我么取走 \(a_i-(a_i\oplus x)\)，使得 \(a_i\leftarrow a_i\oplus x\)。那么新的异或值就是 \(\oplus_{i=1}^n a_i\oplus x=x\oplus x=0\)，抛给对手一个 \(x=0\) 的局面。
对于当前局面若 \(x=0\)，不存在任何方式将其变为 \(0\)：

用反证法，假设存在某种方式，且取走的记为 \(a_i\)，那么有 \(\oplus_{j=1}^n a_i=0\)，且 \(\oplus_{j=1}^{i-1} a_j\oplus a_i'\oplus_{j=i+1}^{n} a_j=0\)，两个式子异或，其余的数都消去，剩下 \(a_i\oplus a_i'=0\)，即 \(a_i=a_i'\)，而至少要取走一个，所以不存在任何方式。