原题链接

Nim游戏

设n堆石子的个数分别为:$[a_1,a_2,a_3,...,a_n]$，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。

问如果两人都采用最优策略，先手是否必胜。

结论

若 $ a_1 \oplus a_2 \oplus a_3 \oplus ... \oplus a_n \neq 0 $ 则先手必胜
若 $ a_1 \oplus a_2 \oplus a_3 \oplus ... \oplus a_n = 0 $ 则先手必败

证明

1. 当所有石子个数都为0时：$ 0 \oplus 0 \oplus 0 ... \oplus 0 = 0$
2. 当n堆石子的个数分别为:$[a_1,a_2,a_3,...,a_n]$时
   2.1 若 $ a_1 \oplus a_2 \oplus a_3 \oplus ... \oplus a_n = x \neq 0 $
   下证存在一种方法，可以使得$ a_1 \oplus a_2 \oplus a_3 \oplus ... \oplus a_n = 0 $
   假设二进制表示下x的最高位1是第k位，那么在$[a_1,a_2,a_3,...,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 a_3 \oplus ... \oplus a_i ... \oplus a_n \oplus x = x \oplus x = 0 $
   由此可得在2.1情况下，我们可以通过在第i堆石子中拿取$a_i - (a_i \oplus x) 个石子$就可以使得每堆石子的异或值变为0
   2.2 若 $ a_1 \oplus a_2 \oplus a_3 \oplus ... \oplus a_n = 0 $ $(1)$
   下面采用反证法证明无论我们如何操作，异或值都无法保持为0，只能大于0。
   假设我们通过某种操作之后，$a_i$变成了$b_i (b_i < a_i )$
   并且 $ a_1 \oplus a_2 \oplus a_3 \oplus b_i \oplus ... \oplus a_n = 0 $ $(2)$
   此时(1)式 $\oplus$ (2)式 = $ a_1 \oplus a_2 \oplus a_3 \oplus ... \oplus a_n \oplus a_1 \oplus a_2 \oplus a_3 \oplus b_i \oplus ... \oplus a_n = a_i \oplus b_i = 0$
   得到$ a_i \oplus b_i = 0 即 a_i = b_i$ $(3)$
   又因为$ b_i < a_i $ $(4)$
   (3)试与(4)式矛盾，说明无论我们如何操作，异或值都无法保持为0，只能大于0
   3.下证
   若 $ a_1 \oplus a_2 \oplus a_3 \oplus ... \oplus a_n \neq 0 $ 则先手必胜
   若 $ a_1 \oplus a_2 \oplus a_3 \oplus ... \oplus a_n = 0 $ 则先手必败
   3.1 若 $ a_1 \oplus a_2 \oplus a_3 \oplus ... \oplus a_n \neq 0 $，先手选手通过某种操作直接将异或值变为0，而后手选手无论如何操作都无法将异或值保持为0，所以下一轮先手选手开始操作的时候异或值还是不为0，因此先手选手得到的状态永远都大于0，不可能是$ 0 \oplus 0 \oplus 0 ... \oplus 0 = 0$，所以此时先手必胜
   3.2 若 $ a_1 \oplus a_2 \oplus a_3 \oplus ... \oplus a_n = 0 $，先手选手无论如何操作都无法把状态保持为0，后手选手得到的状态永远不为0，所以$ 0 \oplus 0 \oplus 0 ... \oplus 0 = 0$一定会被先手选手遇到，所以此时先手必败

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n,res = 0;
    cin>>n;
    while(n--)
    {
        int x;
        cin>>x;
        res ^= x;
    }
    
    if(res) puts("Yes");
    else puts("No");
    
    return 0;
}