若一个游戏满足：

1. 由两名玩家交替行动
2. 在游戏进行的任意时刻，可以执行的合法行动与轮到哪位玩家无关
3. 不能行动的玩家判负

则称该游戏为一个公平组合游戏。

尼姆游戏（NIM）属于公平组合游戏，但常见的棋类游戏，比如围棋就不是公平组合游戏，因为围棋交战双方分别只能落黑子和白子，胜负判定也比较负责，不满足条件2和3。

题目描述

给定$n$堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。

例如：有两堆石子，第一堆有2个，第二堆有3个，先手必胜。

操作步骤：
1. 先手从第二堆拿走1个，此时第一堆和第二堆数目相同
2. 无论后手怎么拿，先手都在另外一堆石子中取走相同数量的石子即可。

必胜状态和必败状态

在解决这个问题之前，先来了解两个名词：

1. 必胜状态，先手进行某一个操作，留给后手是一个必败状态时，对于先手来说是一个必胜状态。即先手可以走到某一个必败状态。
2. 必败状态，先手无论如何操作，留给后手都是一个必胜状态时，对于先手来说是一个必败状态。即先手走不到任何一个必败状态。

结论

假设$n$堆石子，石子数目分别是$a_1,a_2,…,a_n$，如果$a_1 \oplus a_2 \oplus … \oplus a_n \neq 0$，先手必胜；否则先手必败。

证明

• 操作到最后时，每堆石子数都是$0$，$0 \oplus 0 \oplus … 0 = 0$
• 在操作过程中，如果 $a_1 \oplus a_2 \oplus … \oplus a_n = x \neq 0$。那么玩家必然可以通过拿走某一堆若干个石子将异或结果变为0。
  证明：不妨设x的二进制表示中最高一位1在第k位，那么在$a_1,a_2,…,a_n$中，必然有一个数$a_i$，它的第k为时1，且$a_i \oplus x < a_i$，那么从第$i$堆石子中拿走$(a_i - a_i \oplus x$)个石子，第$i$堆石子还剩$a_i - (a_i - a_i \oplus x) = a_i \oplus x$，此时$a_1 \oplus a_2 \oplus … \oplus a_i \oplus x \oplus… \oplus a_n = x \oplus x = 0$。
• 在操作过程中，如果 $a_1 \oplus a_2 \oplus … \oplus a_n = 0$，那么无论玩家怎么拿，必然会导致最终异或结果不为$0$。
  反证法：假设玩家从第$i$堆石子拿走若干个，结果仍是$0$。不妨设还剩下$a’$个，因为不能不拿，所以$0 \leq a’ < a_i$，且$a_1 \oplus a_2 \oplus … \oplus a’ \oplus… \oplus a_n = 0$。那么$(a_1 \oplus a_2 \oplus … \oplus a_i \oplus… a_n) \oplus (a_1 \oplus a_2 \oplus … \oplus a’ \oplus… \oplus a_n) = a_i \oplus a’ = 0$，则 $a_i = a’$，与假设$0 \leq a’ < a_i$矛盾。

基于上述三个证明：
1. 如果先手面对的局面是$a_1 \oplus a_2 \oplus … \oplus a_n \neq 0$，那么先手总可以通过拿走某一堆若干个石子，将局面变成$a_1 \oplus a_2 \oplus … \oplus a_n = 0$。如此重复，最后一定是后手面临最终没有石子可拿的状态。先手必胜。
2. 如果先手面对的局面是$a_1 \oplus a_2 \oplus … \oplus a_n = 0$，那么无论先手怎么拿，都会将局面变成$a_1 \oplus a_2 \oplus … \oplus a_n \neq 0$，那么后手总可以通过拿走某一堆若干个石子，将局面变成$a_1 \oplus a_2 \oplus … \oplus a_n = 0$。如此重复，最后一定是先手面临最终没有石子可拿的状态。先手必败。

c++代码

#include <iostream>
#include <cstdio>
using namespace std;

/*
先手必胜状态：先手操作完，可以走到某一个必败状态
先手必败状态：先手操作完，走不到任何一个必败状态
先手必败状态：a1 ^ a2 ^ a3 ^ ... ^an = 0
先手必胜状态：a1 ^ a2 ^ a3 ^ ... ^an ≠ 0
*/

int main(){
    int n;
    scanf("%d", &n);
    int res = 0;
    for(int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        res ^= x;
    }
    if(res == 0) puts("No");
    else puts("Yes");
}