其实我自己也不是很明白吧
SG函数应用的场景
组合游戏
在竞赛中，组合游戏的题目一般有以下特点
-
题目描述一般为A，B，2人做游戏
-
A，B交替进行某种游戏规定的操作，每操作一次，选手可以在有限的操作（操作必须合法）集合中任选一种。
-
对于游戏的任何一种可能的局面，合法的操作集合只取决于这个局面本身，不取决于其它因素（跟选手，以前的所有操作无关）
-
如果当前选手无法进行合法的操作，则为负
必胜点和必败点的概念
必败点(P点) 前一个(previous player)选手将取胜的点称为必败点
必胜点(N点) 下一个(next player)选手将取胜的点称为必胜点
SG函数
先定义mex(minimal excludant)运算，这是施加于一个集合的运算，表最小的不属于这个集合的非负整数。例如mex{0,1,2,4}=3
对于任意状态x，定义SG(x) = mex(S),其中S是x后继状态的SG函数值的集合。如x有三个后继状态a，b，c的SG值分别为SG(a)，SG(b)，SG(c)，那么SG(x)=mex{SG(a)，SG(b)，SG(c)}。 这样当我没有后继状态的时候集合S的终态必然是空集，所以SG函数的终态为SG(x)=0，当且仅当x为必败点P时。
虽然我也不知道为什么要这么求，但是数学就是这么神奇呀
SG定理
游戏和的SG函数等于各子游戏的SG函数的Nim和。
公式说明：\(SG(x_1,x_2,x_3\dots x_n) = SG(x_1)\bigoplus SG(x_2)\dots\bigoplus SG(x_n)\)
应用
具体怎么应用呢？我可以递归求出一部分情况的SG值，然后瞪眼发现规律
例题：[SDOI2009]E&D
`