博弈论研究

前置知识这里不会细讲，可以看看这几位大佬的博客和文章，感觉讲得很好。

记住这句话，“每个必胜的状态都是从对手的上个必败状态推来的，必败也是同理。”。

算法学习笔记(51): SG函数 - 知乎 (zhihu.com)

博弈论总结（只会打表，永不证明）（博弈论） - Flash_Hu - 博客园 (cnblogs.com)

题解 P2197 【【模板】nim游戏】 - 洛谷专栏 (luogu.com.cn)

[学习笔记]（博弈论）Nim游戏和SG函数_nim博弈-CSDN博客

浅谈SG函数和博弈论 - 洛谷专栏 (luogu.com.cn)

博弈论 SG函数_a1 ^ a2 ^ … ^ an != 0-CSDN博客

---

这里先用\(Nim\)博弈引入：P2197 【模板】Nim 游戏 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

我们设计当\(SG(x)=0\)时，\(x\)为必败态，相反，\(x\)为必胜态。

对于单堆的\(Nim\)游戏，我们可以计算出\(SG\)值，\(SG(x)\)表示剩余石子数为\(x\)的状态值。

根据\(SG\)函数的定义：\(SG(x)=mex((SG(y)|x->y))\),\(mex\)表示一个集合中未出现的最小自然数。

不难得到，我们可以得到：\(SG(1)=1、SG(2)=2、SG(3)=3······SG(n)=n\)。(从\(SG(0)=0\)递推过来)。

利用\(SG\)定理，我们可以将多个堆的状态转移到一个堆的状态，直接异或起来就行了。

参考代码

//
// Created by 22635 on 2024/2/9.
//
#include<bits/stdc++.h>
using namespace std;
void solve();
int main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
void solve(){
    int n,ans=0;
    cin>>n;
    while(n--){
        int a;
        cin>>a;
        ans^=a;
    }
    if(ans==0){
        cout<<"No\n";
    }
    else{
        cout<<"Yes\n";
    }
}