博弈论

整局游戏，第一个行动的称为先手，第二个行动的称为后手。

讨论，先手必胜的状态，和先手必败的状态

举个例子，两堆石子，{2, 3}

• A先从第2堆里拿1个，变成{2, 2}

• B后从第1堆里拿2个，变成{0, 2}

• A再从第2堆里拿2个，变成{0, 0}

• B无法操作，B失败

这里的规律是，先手保证拿完石子后，让两个石子的状态一样，就能够保证先手必胜。

定理

NIM博弈先手必胜，当且仅当 A1 xor A2 xor … xor An != 0

可使用数学归纳法进行证明

分析

为什么

A1 xor A2 xor … xor An != 0， 先手必胜

A1 xor A2 xor … xor An == 0， 先手必败

缩小问题范围

A1 xor A2 != 0， 先手必胜

A1 xor A2 == 0， 先手必败

从题意出发，当玩家面对{0, 0}状态的时候，就是失败的时候，也就是A1 == A2时候，如果A1 == A2，A1 xor A2 != 0

可是，前面举例子中，先手拿完之后是{2, 2}，也不是{0, 0}啊。注意，{2, 2}也是一个A1 == A2的局面。此时，后手拿多少，我跟着在另外一堆拿多少，就一直可以把面对A1 == A2局面的情况，交给后手面对。随着游戏的进行，最终面对{0, 0}的就是后手。故，先手必胜。

不要问我2堆石子我懂，但是n堆石子我不懂的问题。

我可以这样回答，n堆石子，我也可以两堆两堆的拿完。

一顿分析猛如虎，然而代码二百五

参考代码

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

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

int main()
{
    int T;
    cin >> T;

    while (T--)  //T组测试数据
    {
        int n;
        int res = 0;

        scanf("%d", &n);
        while (n--)  //每组数据中n堆石子，取一遍xor
        {
            int x;
            scanf("%d", &x);
            res ^= x;
        }

        if (res) puts("Yes");  //依据分析先手必胜的局面  
        else puts("No");
    }

    return 0;
}