SG函数是用于解决博弈论中公平组合游戏（ICG）问题的一种方法

ICG

这是啥？

定义大概就几条：

1. 双方参与，轮流决策，决策最优
2. 无法决策时游戏结束，无法决策者输，不论如何决策游戏都能在有限步完成
3. 同一状态不可多次抵达，游戏无平局，任意决策者在决策点的行为与决策者无关仅与决策点有关

这就是 ICG，公平组合游戏

典型例子是 nim 游戏

必胜必败态

必败态：记为 P，直观理解就是到达这个状态的人已经必死无疑了
必胜态：记为 N，直观理解就是到这里就稳了，脑子不犯蠢就一定会赢

可以证明 ICG 里任意状态一定都是这两种状态，有策梅洛定理：

策梅洛定理：ICG 游戏中，任何一个局面先手或者后手其中之一必然存在必胜策略

如何判断一个状态是 N 是 P 呢？

最直观的方法是：

• 无法移动的状态一定是 P，称为初必败态
• 能够移动到必败态的一定是必胜态，因为你只要往必败态走就行了
• 只能移动到必胜态的就是必败态，因为你无论如何行动对手都必胜了

DAG的博弈

有这样一个问题

给定一个有向无环图，在给定的起点处有一个棋子，两个炒鸡聪明的人交替移动这个棋子，不能移动者输

看起来是一个很呆的问题，但是这个问题单独拿出来的意义在于 任意一个 ICG 问题都可以归纳到这种形式（状态为点，状态间连边）

mex运算

马上要开始探究 SG 函数，但是在此之前......

首先我们需要定义一个奇怪的运算，mex

这是一个数集的运算符号，\(mex(S)\) 代表的是不在集合 \(S\) 中 的最小自然数

例如 \(mex(\{0,1,3,5\})=2\)

SG函数

用 \(v(u,v)\) 表示从 \(u\) 到 \(v\)，存在直接的有向边，则

对于给定的 DAG，我们定义每个点的SG函数为：

\(SG(x)=mex(\{SG(y)|v(x,y)\})\)

但是只有这一个函数呢，他是啥用么有的

SG函数的性质

• 所有汇点（也就是各个初必败态）的 \(SG\) 函数值为 \(0\)

这个应该比较显然的说，因为此时后继状态都是空集

• \(SG(x)=0\) 是 \(x\) 为必败态的充要条件，\(SG(x)\neq 0\) 是 \(x\) 是必胜态的充要条件

以上就是一维 \(SG\) 函数的基本内容，利用这个例子我们可以解决一个简单的经典小问题

巴什博弈：一堆石子有 \(n\) 个，每次可以取 \([1,m]\) 个石子。先取完者获胜。问何时先手必胜，何时后手必胜？

发现暴力算是可以解决的

如果追求效率，经常不会真的去暴力算 \(SG\)，而是考虑直接归纳每个状态的 \(SG\) 函数

如果算一遍 \(SG\) 的代价可以承受，就可以考虑直接去算

但是如果不能归纳出 \(SG\) 函数，这种博弈问题我们就是不能得出结论通解的

先介绍一下考场实用的一种方法：打表

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;

int n,m;
int SG[N];
bitset<N> S,clr;
void get_SG(){
    SG[0]=0;
    for(int i=1;i<=n;i++){
        S&=clr;
        for(int j=1;j<=min(m,i);j++){
            S[SG[i-j]]=1;
        }
        for(int j=0;;j++){
            if(!S[j]) {SG[i]=j;break;}
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    get_SG();
    for(int i=1;i<=n;i++) cout<<SG[i]<<endl;
}

根据定义，这份代码可以打出巴什博弈的 \(SG\) 函数

我们可以观察出 \(SG\) 在巴什博弈的规律是 \(SG(x)=x\bmod (m+1)\)，这是我们观察出的结论

一般我们可以打出表来，然后再证明（当然不证也不是啥大事，只要你多看看确认是对的就行）

巴什博弈的证明是显然的，就不赘述了

SG定理

如果 \(SG\) 只能解决一维的博弈问题，那这个玩意其实有点弱了

nim游戏

先用一个简单的例子来引入一下

nim game

这是一个可拆分的组合游戏

我们考虑一个子游戏，即考虑拿出任意一堆来做游戏

我们称 \(SG(x)\) 表示大小为 \(x\) 的堆的 \(SG\) 函数，显然有 \(SG(x)=x\)

我们很容易得出面前的每一堆的子游戏是必胜还是必败

尝试用子问题的胜败推出总问题的胜败！

这里先考虑两个子问题的复合，因为多个子问题本质上就是两个的情况的扩展

• 当我面前两个游戏都是必败的，则我必败

    必败的走一步必然走到必胜的
  
    等会对面再把另一个变成必败的，我又收到了两个必败游戏
  
    最后我会收到两个无子可动的终盘游戏，则我必败
  

• 假如我面前摆着一败一胜的游戏，实际上我必胜

    必胜的走一步能走到必败的
  
    对面会收到两个必败，对面一定会输
    
    故我必胜
  

• 假如面前是两个必胜......

等会，好像不太对劲

两个必胜在我面前时，我根本无法判断我必胜还是必败

有点悲哀，好像寄了，单个的 \(SG\) 函数貌似无法直接复合生成，那难道没有办法了吗

SG定理

此时某位我不知道是谁的伟大的人给出了一个伟大的定理，SG定理

SG定理：游戏的“和”（其实是复合）的 \(SG\) 值是各个子问题 \(SG\) 的异或和

然后我们可以发现这个问题我们解决了！

于是nim游戏的 \(SG\) 已经非常简单的搞定了

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int n;
int a[N];
int T;
void work(){
    cin>>n;
    int xr=0;
    for(int i=1;i<=n;i++)cin>>a[i],xr^=a[i];
    if(xr==0) cout<<"No\n";
    else cout<<"Yes\n";
}
int main(){
    cin>>T;
    while(T--){
        work();
    }
}

短小精悍

证明不会