$\huge \color{orange}{成仙之路->}$ $\huge \color{purple}{算法基础课题解}$

Nim游戏

结论： $若\ a_1 \bigoplus a_2 \bigoplus … \bigoplus a_n=0,\ 则先手必败,反之先手必胜$

概念：

• 必败状态：无法走到任何一个必败状态
• 必胜状态：可以走到某一个必败状态

证明：

• 第一步

$操作到最后，游戏必定能够结束，即\ 0 \bigoplus 0 \bigoplus … \bigoplus 0=0$

• 第二步

$假设\ a_1 \bigoplus a_2 \bigoplus … \bigoplus a_n=0为必败状态，反之为必胜状态$

$假设从\ a_i\ 中拿走部分石子变为\ a_{i’}\ 后依旧为必败状态，即\ a_1 \bigoplus a_2 \bigoplus …\bigoplus a_{i’}\bigoplus… \bigoplus a_n= 0$

$则\ a_i \bigoplus a_{i’}=0，即\ a_i=a_{i’},故假设不成立，即必败状态：无法走到任何一个必败状态$

• 第三步

$假设必胜状态\ a_1 \bigoplus a_2 \bigoplus … \bigoplus a_n=x的二进制最高位在第k位,则必存在a_i的第k位为1，则a_i\bigoplus x<a_i$

$那么我们在第i堆石子取走 \ a_i-(a_i\bigoplus x) \ 后则变为\ a_i\bigoplus x$

$则\ a_1 \bigoplus a_2 \bigoplus …\bigoplus a_{i}\bigoplus x \bigoplus… \bigoplus a_n=x\bigoplus x = 0，即必胜状态：可以走到某一个必败状态$

• 综上即可得出结论

完整代码

#include<bits/stdc++.h>

using namespace std;

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

    int res=0;
    while(n--)
    {
        int x;
        cin>>x;
        res^=x;
    }

    if(res) puts("Yes");
    else puts("No");

    return 0;
}