SG函数
SG function & SG theorem
文中证明皆为擢发数根所得，纰漏在所难免，请不吝赐教。
先介绍一些相关的定义。
ICG （公平组合游戏）
抽象模型：
给定一个有向无环图和一个起始顶点上的一枚棋子，玩家交替的将这枚棋子沿有向边进行移动，无法移动者判负。问是否有必胜策略。
P-position & N-position
定义
P：当前局面先手必败 N：当前局面先手必胜
以上都是指双方采取最优策略的情况。
性质
- 无法进行任何移动的局面（terminal position）是P-position；（死局，败）
- 可以移动到P-position的局面是N-position；（有办法让对方败）
- 所有移动都导致N-position的局面是P-position。（无路可走）
operation mex
mex（minimal excludant）是定义在整数集合上的操作。它的自变量是任意整数集合，函数值是不属于该集合的最小自然数。
mex{A}=min{k | k?A且k∈N}
这个操作在下面会用到。
SG function
SG函数是用于评价某个局面形势的函数，适用于任意ICG。
定义
对于一个游戏对应的有向无环图中的节点x，
sg(x)=mex{ sg(y) | y为x的后继（即存在边x->y） }
性质
没有出边的顶点，其SG值为0
对于x | sg(x)=0，其所有后继y都满足 sg(y)≠ 0。
对于x | sg(x)≠ 0，必定存在后继y满足sg(y)=0。
x为P-position <=> sg(x)=0，x为N-position <=> sg(x)≠0
说明：
首先没有出边的顶点先手必败是显然的。
对于任意一个sg(x)≠0的顶点，由性质3知存在y | sg(y)=0，那么先手选择移动到y。由性质2，后手在y只能选择z | sg(z)≠0。所以先手面临的总是sg(x)≠0的局面，后手总是sg(x)=0的局面，循环下去后手一定会先到达一个没有出边的点，败。
对于任意一个sg(x)=0的顶点，可以用类似的方法
伪证。游戏和：
若原游戏G可以分解成多个子游戏gi，则原游戏的sg值为子游戏sg值异或和。 即： sg(G)=sg(g1)^sg(g2)^sg(g3)^…^sg(gn) 所以若 sg1^sg2^…^sgn=0，则后手有必胜策略。
接下来介绍几种类型的博弈游戏。
Nim Game(stone)
经典Nim游戏
example: luogu2197
取石子游戏
n堆石子，两人轮流取走石子。 每次只能从一堆中取出任意数目的石子，但不能不取。 取走最后一个石子者胜。
分析
首先将原游戏分解为n个一堆a个石子的子游戏，那么一共存在0~a种局面，对应剩下0~a个石子。下面用第二归纳法证明对剩下x个石子的情况，sg(x)=x。
证明：
x=0时，先手没有办法操作，故sg(0)=0；
假设0<=x<=k时，均有sg(x)=x，
sg(k+1)=mex{sg(0),sg(1),…,sg(k)}=mex{0,1,…,k}=k+1。
由1、2及归纳法知，sg(x)=x对任意x∈N成立。
再根据游戏和的概念，考虑n堆石子数分别为a1,a2…an的石子堆，有sg(G)=sg(a1)^sg(a2)^…^sg(an)。
所以当sg(G)=a1^a2^…^an=0时，后手有必胜策略。
必胜策略
上面只讨论了有必胜策略的充要条件，下面给出具体的取胜的方法。
- 对于后手且sg(G)=0，直观地看，要一直保持上风并且直到游戏的胜利，需要在对方取石子后将局面复原到sg(G)=0的情况；
- 对于先手且sg(G)≠0，那么显然要使得自己取之后局面变成sg(G)=0，然后同上。
因此主要问题就是对于一个sg(G)≠0的情况，如何取使得sg(G)=0。
我们从二进制异或的角度考虑。
设最终异或的结果的二进制表示为sg(G)=x[0]*2^0+x[1]*2^1+…，且其中x[b1]，x[b2]…x[bm]值为1。
下面要寻找某堆石子a（显然a>=2^bm）与x，从a中取x后，可以使得所有x[bj]变为0且其他x[i]不变。
设a=y[0]*2^0+y[1]*2^1+…。需要注意的是，这里a中对应x[bj]的y[bj]不一定为1，因为还有其他石子堆。
根据异或的性质可以得到两个结论：
- 要改变结果的某一位，只要改变a中对应二进制位（0->1,1->0）即可；
- x[bm]=1，则存在a使得y[bm]=1。
下面说明对于满足结论2的a，一定可以实现操作1。
由于y[bm]=1，所以在操作1中一定要将y[bm]置为0。因此无论后面的y[bj]是从1变为0还是从0变为1，所得到的a’一定满足a’<a。又根据异或运算，操作1等价于：a’=a^sg(G)。
所以只要从a中取x=a-a^sg(G)个石子，就可以实现使sg(G’)=0的要求。
变形
限制qu
每堆最多取k个
将每堆物品数mod(k+1)；
可选步数为一系列不连续的数（e.g.：poj2960 ）
设可以取的数为m1,m2,…,
对于a个石子，其后继分别为a-m1,a-m2,…a-mi。
于是就可以构造出一个有向无环图，再用mex操作预处理出任意sg(a)。
AntiNim
取到最后一粒石子的人算输
Sprague-Grundy Theorem
内容：任意ICG可以等价为唯一一个Nim游戏。
树上删边游戏
叶子节点的SG值为0； 中间节点的SG值为它的所有子节点的SG值加1后的异或和
Fusion Principle
我们可以对无向图做如下改动：将图中的任意一个偶环缩成一个新点，任意一个奇环缩成一个新点加一个新边；所有连到原先环上的边全部改为与新点相连。这样的改动不会影响图的SG值。
参考资料
IOI2009国家集训队论文 贾志豪《组合游戏略述——浅谈SG游戏的若干拓展及变形》
https://blog.csdn.net/A_Comme_Amour/article/details/79347291