SG定理&SG函数
概念:
必胜点N:
在此位必胜
必败点P:
在此位必输
更严谨的定义为：
无法移动的状态(即terminal-position)为P
可以移动到P的局面为N
所有移动都会进入N的局面为P
性质:
1.所有终结点一定是[必败点P]
2.从任意[必胜点N]开始操作，至少有一种方式进入必败点P
3.无论如何操作，[必败点P]只能进入[必胜点N]
胜态和败态的关键性质：经过一步行动，败态只能变成胜态，胜态可以（但不一定）变成败态。
定义SG(x)=mex(S),S是x的后继状态的SG函数集合
mex函数:
mex(S)表示不在S内的最小非负整数 例如mex{1,2,3}=0，mex{0,2}=1，mex{0,1,2,3}=4，mex{}=0
不难发现，当且仅当x为必败状态，SG(x)=0
Sprague-Grundy定理(SG定理):
游戏和的SG函数等于各个子游戏SG函数的Nim和
对于给定的有向无环图，定义每个点的SG函数为:SG(x)=mex{ SG(y) | x can go to y}
ICG游戏:
1.游戏有两个人参与，二者轮流做出决策。且这两个人的决策都对自己最有利。
2.当有一人无法做出决策时游戏结束，无法做出决策的人输。无论二者如何做出决策，游戏可以在有限步内结束。
3.游戏中的同一个状态不可能多次抵达。且游戏不会有平局出现。
任意一个游戏者在某一确定状态可以作出的决策集合只与当前的状态有关，而与游戏者无关。
满足上述条件的问题我们称之为ICG游戏，ICG游戏属于组合游戏
最典型的nim游戏，就是一种ICG游戏
DAG(有向无环图)中的博弈:
在正式研究SG函数之前，我们先来研究一下DAG中的博弈
给定一张有向无环图，在起始定点有一枚棋子，两个顶尖聪明的人交替移动这枚棋子，不能移动的人算输
不要小看这个游戏,事实上,所有ICG问题都可以抽象为这种游戏(即把初始局面看做顶点,把从一个状态可以到另一个状态之间连边)
策梅洛定理（Zermelo's theorem）
指出，若一个游戏满足如下条件：
1.双人、回合制；
2.信息完全公开（perfect information）；
3.无随机因素（deterministic）；
4.必然在有限步内结束；
5.没有平局；
则游戏中的任何一个状态，要么先手有必胜策略，要么后手有必胜策略（下文把这两种状态分别称为“胜态”、“败态”）。
nim游戏[模板]:
地上有 nn 堆石子每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。
每次只能从一堆里取。最后没石子可取的人就输了。存在先手必胜策略则输出 Yes，否则输出 No
#include <bits/stdc++.h>
using namespace std;
int T,n;
int a[10001];
int main() {
scanf("%d",&T);
while(T--){
int ans=0;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
ans^=a[i];
}
printf(ans?"Yes\n":"No\n");
}
return 0;
}
对于NIM游戏，相信大家都知道一个结论：
Bouton定理:每一堆石子的数量给异或起来，若为0则先手必败，否则先手必胜。这个结论就是Bouton定理。
Bouton定理的证明
参见《算法竞赛·入门经典·训练指南》P135
然后是关于nim游戏的自己理解:
前提:双方都十分的聪明!!!!! 显然可以考虑到对于所有决策的最完美决策方案
首先不难发现胜负与完美操作次数的奇偶性有关
nim游戏有这样一个结论:每个石子堆数量[异或和]为0先手必输，反之必胜
将每个数的[异或和]计算出来可以有什么用呢 ?
我们先把所有堆中的二进制写出来
每次都可以在堆中有1的地方取一个1，或者取多个
这样对于每个堆的每一位，如果有偶数个1
那么不难发现取这位会被来回循环掉，回到原来的决策状态，那么这些贡献可以[忽略]
但如果只有这些每个对应位上偶数个1的话，也就是[异或和]为0的情况，先后手来回循环之后先手必输
但假如不止那些1，还有一些位上有奇数个1的话，就是[异或和]不为0的情况
我可以让先手取掉一些1，此时要分讨:
1.[异或和]有奇数个1，一个一个取，与后手来回取，最后自己取掉最后一个1，是的异或和为0
2.[异或和]有偶数个1，先手取掉一个数使[异或和]仍然为偶数个1，消掉之前一个1，然后就返回到了奇数个1的情况
上面的并没有解释这样一个问题:
为什么取数的过程为什么等价于取1 ?
首先我们可以这样想，取1可以拆分成取多次把一个1取掉，
但是实际上取2次即可，因为假如对方取的不是1，那在循环内部[先手]已经通过之前操作成为了[后手]
每次取的时候取一个能与前面凑成一个1的数即可，循环之后仍然先手胜
[异或和]为0的时候，先手无法改变他始终是“先手”的事实，处在被对方控制的范围内，必输
而[异或和]不为0时，先后可以改变自己为“后手”，场面可控，对于对方决策自己总有方法应对，必胜
如果是对手是取多个1的情况，那么我先手只要与对手取的1的数量凑成偶数，循环下去，还是必胜
来自知乎 10170 Sprague-Grundy定理是怎么想出来的
来自知乎的迷之语句:
下面讨论状态的组合对胜负的影响。
请温习一下胜态和败态的关键性质：经过一步行动，败态只能变成胜态，胜态可以（但不一定）变成败态。
先看两个败态的组合。两个败态的组合还是败态。从后手玩家的角度来看，先手玩家的行动只能将两个败态中的一个改变为胜态，
于是后手玩家可以再将这个胜态变成败态，从而将两个败态的组合抛回给先手玩家。
由于终局状态为败态，最终先手玩家必将面对两个终局状态组成的败态，故后手必胜。
再看一胜一败两个状态的组合。胜态与败态的组合还是胜态——先手玩家只要把胜态变成败态，就可以把两个败态组合成的败态抛给后手玩家了。
最后看两个胜态的组合。这种组合就比较复杂了：先手玩家不应把其中一个胜态变成败态，因为这样会把一胜一败两个状态组合成的胜态留给对方。
因此，先手玩家应当把其中一个胜态变成一个新的胜态。后手玩家面对新的胜态+胜态的组合，应当采取相同的策略。
然而，由于游戏是有限的，早晚会有一个玩家只能把一个胜态变成败态，从而输掉游戏，但我们并不知道这会在哪一步发生。
也就是说，仅仅知道两个子状态都是胜态，不足以推出母状态的胜负；我们需要挖掘胜态的更多性质。