Nim游戏

基础模型

$n$堆物品，每堆有$a[i]$个，两个玩家轮流取走任意一堆的任意数量的物品，但不能不取。取走最后一个物品的人获胜，或者说谁最后没得选就输了。

结论

如果每一堆石子异或和不为$0$的话，那么先手必赢，否则后手必赢。

证明

玩家可以做的操作是对这$n$堆中的一堆中的石子进行选择，使得这堆石子的数量减少，这种减少的操作实际上我们也可以看作一个数$x$堆这堆石子的数量$a[i]$进行异或。

游戏中也只会出现两种局面:

• 情况1：$a_{1} \oplus a_{2} \oplus a_{3} ... \oplus a_{n} \neq 0$ ，一定存在一个数（也就是这些数异或和，假设该数为$k$）使得异或和为$0$，并且能够保证一定存在一个$a[i]$符合$a[i] \oplus k < a[i]$，因为二进制下的$k$的最高位一定是$1$，这说明一定有一个$a[i]$的二进制表示下这一个位置也是$1$,那么让这一个$a[i]$与k异或一定能使得$a[i] \oplus k < a[i]$成立。
• 情况2：$a_{1} \oplus a_{2} \oplus a_{3} ... \oplus a_{n} = 0$，因为每次不能不选，所以无论如何操作一定会破坏异或和为$0$的情况

综上，可以看出如果一个人能够始终处于情况2下，那么这个人必输，先来看情况1，通过一次异或我们发现情况1就可以转化为情况2，由此看出：

• 情况1：先手必赢，后手必输。
• *情况2：先手必输，后手必赢。