$\Huge\color{orchid}{点击此处获取更多干货}$

Nim游戏

Nim游戏是博弈论中最简单的模型，它本身属于公平组合游戏($\text{Impartial Combination Game}$)的一种，它一般满足3个条件：
1. 两位玩家交替从有限的合法移动集合中选择一种，对游戏进行移动；
2. 合法移动集合只取决于游戏局面本身，不受当前移动者、过去的某种局面以及其他随机因素如色子点数等（不符合该条件的一个典例就是象棋，其合法移动集合受到当前移动者和过去某种局面的影响，因为红方只能移动红棋，黑方只能移动黑棋，并且不允许相同局面出现多次）；
3. 合法移动集合为空，即无法进行任何移动时，当前轮到的玩家失败。

对于游戏中的所有石子堆来说，当每一堆石子都空了的时候，合法移动集合就一定为空了，所以游戏的主要目标就是尽力引导另一位玩家，使其在某次移动时出现全空了的状态，因此需要定义两种状态：本家必胜状态($\text{N-Position}$)和上家必胜状态($\text{P-Position}$)。任何一种游戏状态都可以按照以下3条规则判断是$P$还是$N$：
1. 无法进行任何移动的为$P$；
2. $N$一定存在某种变为$P$的合法移动方式；
3. $P$的所有合法移动都将转化为$N$，不存在任何一种保持$P$的移动方式。

先从某些特殊情况开始，假定初始盘面为$\{2,3\}$，那么先手玩家只要从第2堆石子中移走1枚变为$\{2,2\}$，后手玩家无论取哪一堆，数量如何，先手只要能保证两堆石子数量相同，后手必败，那么局面$\{2,3\}$就是一个$\text{N-Position}$，而$\{2,2\}$就是一个$\text{P-Position}$。对于两堆石子而言，两堆的数量相同时为$P$，不同时为$N$。

换一种方式思考，当两堆石子的数量$\{n_1,n_2\}$不同时，假设$n_1>n_2$，那么$n_1$就可以视作两个子堆$\{n_1-n_2, n_2\}$，有两个$n_2$可以一一对应，而剩余的$n_1-n_2$没有与其对应的另一堆，该状态为$N$；而当先手玩家取走$n_1-n_2$个石子之后，留下的局面就只剩之前互相对应的两堆$n_2$，该状态为$P$。由此可以得出一个结论，按照某种划分方式将每堆划分为若干子堆后，每一个子堆都可以与另一个相同大小的子堆对应的局面为$P$，存在某些无法找到对应子堆的局面为$N$

如此一来就可以向堆数更多的情况扩展。利用二进制的思想，每一堆都可以分解为若干数量为2的幂次的子堆，如$25_{10}=11001_{2}$，那么25就可以视作$\{16,8,1\}$即$\{2^4, 2^3, 2^0\}$。对于任意局面$\{a_1,a_2,…,a_n\}$，将每一堆的数量$a_i$转化为二进制数$b_{mi}b_{(m-1)i}…b_{1i}b_{0i}$，那么大小相等的子堆数量为偶数时，每一个子堆都可以与另一个相同大小的子堆一一对应，而大小相等的子堆数量为奇数时，就会存在某些子堆无法找到对应关系。

下面以局面$\{7,9,15,12\}$为例：

很显然，它们二进制的每一位上，1的数量之和不全是偶数，对于大小为$8,4,1$的子堆来说，它们的数量为奇数，只有大小为2的子堆数量才是偶数，此时的状态为$N$。先手玩家从12的一堆中拿走11，就变成了$\{7,9,15,1\}$的$P$状态。

此后无论后手玩家拿多少，先手玩家只要保证和后手玩家拿的数量相同，就可以将全空的$P$状态交给后手玩家。下面是游戏进行的完整步骤：

上面提到的子堆其实就是二进制位的1，每一位上1的数量的奇偶性决定了该位进行异或$(xor)$运算后的结果是1还是0，奇数是1，偶数是0。对初始局面中每一堆的数量两两异或后，如果结果的每一位都是0，就说明该局面是$P$状态，否则为$N$状态，由此得到了$\text{Nim}$游戏的重要结论即包顿定理$\text{(Bouton’s Theorem)}$：对于局面$\{a_0, a_1,…,a_{n-1},a_n\}$，令$Sn=a_0~xor~a_1~xor~…~xor~a_n$，那么$Sn=0$的局面为$P$即后手必胜，而$Sn\ne 0$的局面为$N$即先手必胜。

C++ 代码

代码很简单，但是背后原理有点复杂，参考了博客园的一些帖子，以及提出包顿定理的论文$\text{Nim, A Game with a Complete Mathematical Theory}$之后，完成了本帖

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    size_t x, ans = 0;
    while (n--) {
        cin >> x;
        ans ^= x;
    }
    cout << ((ans != 0) ? "Yes" : "No") << endl;
    return 0;
}