Acwing 891. Nim游戏

先手必胜态：可以走到某一个必败状态
先手必败态：走不到任何一个必败状态

a1, a2, ... , an

a1 ^ a2 ^ ... ^ an = 0,  先手必败

a1 ^ a2 ^ ... ^ an != 0, 先手必胜

证明：

① 当一个石子都没有（每一堆石子都是0时），0 ^ 0 ^ 0 ^ ... ^ 0 = 0

当我们走到终点，不能进行任何 *** 作时，它的异或值为0

② 当a1 ^ a2 ^ ... ^ an = x != 0，一定存在一种方式，可以将它们变成0

假设x的二进制表示中，最高一位1在第k位，由此推出，

a1~an中必然存在一个数ai，ai的第k位是1

显然，ai ^ x < ai（因为x的最高一位1在第k位），两者异或后，把ai的第k位1给消成0了

 然后，我们在ai那一堆拿走ai - (ai ^ x)个石子，此时这一堆剩余ai ^ x个石子

（意思就是，拿走一些石子，使得数量由ai变成ai ^ x）

 所以，必然存在一种方式，拿完一堆石子后，使得剩下的所有数异或起来为0

③ a1 ^ a2 ^ ... ^ an = 0，不管怎么去拿，拿完之后所有数的异或值一定不是0

反证法，假设从第i堆拿完之后，剩下所有数的异或值是0

 把上下两个等式左右两边异或起来，则有，

 说明，ai = ai'，

又因为是在ai中拿走了一部分，所以ai' < ai，推出矛盾

 

/*

先手必胜态：可以走到某一个必败状态
先手必败态：走不到任何一个必败状态

*/
#include 

using namespace std;

int main()
{
    int n;
    scanf("%d", &n);
    
    int res = 0;
    while (n --)
    {
        int x;
        scanf("%d", &x);
        
        res = res ^ x;
    }
    
    if (res) printf("Yes");
    else printf("No");
    
    return 0;
}