SG函数
扯淡
能干啥：
处理一些博弈中的问题。
定义：
一个状态可以推导到的所有后继状态的SG值的mex。
我们知道，一般来说，博弈游戏的状态图是一张DAG。
一个例子
给定一个有向无环图和一个起始顶点上的一枚棋子，两名选手交替的将这枚棋子沿有向边进行移动，无法移动者判负。
我们处理出一个点的SG值。也就是说，把一个点视为一个状态。
那么没有出边的点的SG值为0。那么这是一个必败局面。
接下来我们发现：
如果一个点的SG值不为0，那么其可以推导到一个必败局面，此局面为必胜局面。
如果一个点的SG值为0，那么其推导到的所有局面都是必胜局面，此局面为必败局面。
于是我们得到结论：
因此当前状态为必胜态当且仅当棋子在SG函数值不为0的点上。
一个发现
若一个局面x，其sg(x)>0，则一定存在一个后续局面y，sg(y)=0。
若一个局面x，其sg(x)=0，则x的所有后续局面y，sg(y)>0。
这与必胜局面-必败局面的性质是一样的。
也就是说，如果SG=0的时候这个局面必败。那么就可以得到：
如果SG=0，则此局面必败，反则此局面必胜。
而满足上面条件“SG=0的时候这个局面必败”的，一般是“轮流操作，不能操作为败”的博弈游戏。
那么我们得到这种模型的SG函数的一个性质。即“SG=0则必败”。
拓展
给定一个有向无环图和一些棋子，每个棋子都有一个初始位置。两名选手交替操作，每次操作可以选择一枚棋子并将其沿有向边进行移动，无法移动者判负。
同样，视一个点为状态。
那么，当我们移动的某一枚棋子的SG值是k时，我们可以把它变成0到k-1之间的任意正整数，但绝对不能保持k不变。
那么就是Nim游戏了。把所有SG值处理出来，做异或即可。
BZOJ 1874
给定n堆石子，其中第i堆的石子数目为a[i]。两人轮流操作，每次操作可以选择一堆，取走x个石子，其中x必须是集合B中的数，不能操作者判负。问是否有先手必胜策略。
思路：
我们发现建图就是上面的模型了。
其实事实上是不用把图建出来的。
在引入SG定理之后，会有另一种理解。
SG定理
对于多个单一游戏，X=x[1..n]，每一次我们只能改变其中一个单一游戏的局面。则其总局面的sg值等于这些单一游戏的sg值异或和。
此证明我们可以看看hihocoder的解释：
要证明这一点我们只要证明：
(1) 假设sg(x[1]) xor sg(x[2]) xor … xor sg(x[n]) = A，对于任意一个0 <= B < A，总存在一个X的后续局面Y，使得sg(Y) = B。
(2) 假设sg(x[1]) xor sg(x[2]) xor … xor sg(x[n]) = A，不存在一个X的后续局面Y，使得sg(Y) = A。
下先证明(1)：
假设M = A xor B，设M表示为二进制之后最高位的1为第k位。所以A的第k位为1，B的第k位为0。又因为A的第k位为1，至少存在一个i，sg(x[i])的第k位也为1。那么一定有sg(x[i]) xor M < sg(x[i])，即一定通过某个操作使x[i]变为x[i']，且sg(x[i']) = sg(x[i]) xor M。那么：
sg(x[i']) xor Other = sg(x[i]) xor M xor Other = M xor A = B
下证明(2)：
若sg(X) = A，sg(Y) = A。不妨设我们改变的游戏为x[i]，则X=x[1..n], Y=x[1…i'…n]。有sg(x[i]) = sg(x[i'])，产生矛盾，所以sg(Y)不可能等于A。
这也很类似于Nim游戏的证明方法。
Nim游戏
局面上一共有N堆石子，每一次我们只能改变一堆石子。那么我们可以将每一堆石子看作一个单一游戏。
对于一堆数量为x的石子的SG函数值，等于其后继状态的SG函数值的mex。即SG(x)=mex{SG(x-1),SG(x-2)...SG(1),SG(0)}。注意这里不能再把一堆石子视为总状态用SG定理，因为一次会改变多个石子（子状态），不满足SG定理的条件。
我们预处理数量为x的SG函数值，发现SG(x)=x。
于是总状态的SG函数值=每一堆石子的SG函数值的异或和=每一堆石子的个数的异或和。
由于这个游戏是“轮流操作，不能操作者必败”的模型，所以得到了Nim游戏的结论：
如果石子堆的个数的异或和为0，那么此局面必败。
hihocoder#1173
在Nim游戏中新增一条规则：
可以选择把一个石子堆分裂为两堆非空的石子堆。
思路：
这是一样的模型，于是我们得到：如果SG=0，则必败，反则必胜。
接下来，我们来讨论SG函数值。
发现一次只会改变一个石子堆，那么把石子堆当做子局面再好不过了。
即：最终局面是总局面，一堆石子是子局面。一次只会改变一个子局面，所以根据SG定理，有：
SG(最终局面)=SG(每一堆石子)的异或和
接下来考虑求一堆石子的SG值。
这一堆石子有两种后继状态：
分堆
不分堆
假设这一堆石子有x个。
对于不分堆的，这一堆石子会变为0,1...x-1。
对于分堆的，假设其分为了一堆大小为i与一堆大小为x-i的石子堆。那么这一个状态的SG函数值为SG(i) xor SG(x-i)。
至于原因，我们可以参考总局面的分析。这个状态只是一个规模较小的总局面而已。
所以对于一堆大小为x的石子，我们可以得到
SG(x)=mex{SG(0),SG(i),SG(i) xor SG(x-i)|1<=i<=x-1}
这就是此题的公式。
BZOJ 1188
给定n堆石子从左到右排列，每次你可以选择一堆石子，从中取出一个石子，然后在它右边任选两堆（可以相同），并往这两堆中各放一个石子。不能操作者判负。
求先手是否有必胜策略。如果有必胜策略，要求输出字典序最小的第一步操作。
思路：
在这里只讨论第一问。
首先我们发现一次操作会对多堆石子造成影响。那么不能直接上SG定理。
我们把游戏视为一个石子分裂开来，变为两枚石子坐落到右边的石子堆
这样一次操作就只会对一枚石子造成影响了。（当然对于一堆石子同样可以这样考虑，只是那样的话SG值不好计算），即
SG(总局面)=SG(石子的移动（分裂）)
接下来我们发现，一个石子的移动（分裂）是通过位置来体现的，而不是像上题中，“一堆石子的改变通过石子的个数来体现”。
所以我们也可以这样表示：
SG(总局面)=SG(石子的位置)
接下来，对于一个在位置p的石子，假设分裂之后，到了位置i与位置j，那么我们可以得到这个状态的SG值是SG(i) xor SG(j)。
至于原因，我们同样可以参考上题中最后一部分的推导。类比对总局面的分析，这个状态只是一个规模比较小的总局面而已。
所以对于一枚位置在p的石子，我们可以得到
SG(p)=mex{SG(i) xor SG(j)|i,j>p}
这就是此题的公式。
BZOJ 1457
给定一张100*100的棋盘，在上面有一些“皇后”（可能有多个皇后在同一位置），两人轮流操作。
每次操作可以选择一个皇后进行移动，但不能使其横或纵坐标变大，也不能原地不动。
先将任意一个皇后移动至(0,0)者判胜。求先手是否有必胜策略。
思路：
此题不是无法操作者为败。
关键在于转换。我们发现如果走到了禁区，也就是下一步就可以胜利的，那么本方玩家就输了。
所以问题转换为：不走到禁区，无法操作者为败。
发现状态的转移是一张有向无环图。
当然，由于一次只会移动一枚棋子，我们可以把一个皇后单独拿出来考虑。之后变为处理每一个位置的SG函数值，最后xor即可。