1.公平组合游戏(ICG)

定义：

两名选手 两名选手轮流行动，每一次行动可以在有限合法操作集合中选择一个 游戏的任何一种可能的局面(position)，合法操作集合只取决于这个局面本身，不取决于轮到哪名选手操作、以前的任何操作、骰子的点数或者其它因素；局面的改变称为“移动”(move) 如果轮到某名选手移动，且这个局面的合法的移动集合为空（也就是说此时无法进行移动），则这名选手负

摘自博客 局面划分： P-position :在当前局面下，先手必负 N-position：在当前局面下，先手必胜 它们的性质 1.当前合法操作集合为空，则当前局面为P-position 2.如果可以移动到P-position，那么当前局面为N-position 3.所有只能移动到N-position的局面都是P-position 至于为什么，因为是两个人轮流行动，所以局面一定是交替的出现，所以以上结论显然成立。 算法实现：

1.标记所有终止局面为p 2.将一部操作可以进入p的局面标记为n 3.如果从一个局面开始，所有可以进入的局面都是n，那么这个局面是p 4.如果3未能找到新的p，那么算法终止。否则返回2.

对于这到题：luoguP2197 有一个很有趣的结论

对于一个局面A1 xor A2 xor A3 … xor An =0 的时候是一个p局面 证明： 如果石子数量为0，那么此时先手必输 如果所有石子异或和为k，k的二进制最高位的1为第j位。那么我们找一个数ai，使得ai的最高位为j，然后取走石子，把ai变为ai xor k，那么所有数的异或和为0. 如果他们的异或和不为0，且存在数量不为0的石子堆，那么显然不能找到一种方法使得异或和仍然为0。

有向图游戏

给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判负。该游戏被称为有向图游戏。 任何一个公平组合游戏都可以转化为有向图游戏。就是把每个局面看成有向图中的一个节点，然后进行移动就行了！

Mex运算

他是一个作用于集合的运算。设S表示一个非负整数集合。定义mex(S)为求出不属于集合S的最小非负整数运算，即：\(mes(S)=min_{x\in N,x\notin S}{(x)}\)

SG函数

在有向图游戏中，对于每个节点$x$,设从$x$出发共有$k$条有向边，分别到达节点$y_1,y_2,y_3…,y_k$,定义SG(x)为$x$的后继节点$y_1,y_2,…y_k$的SG函数构成的集合在执行mex运算的结果，即: \(SG(x) = mex(\{SG(y_1),SG(y_2),...,SG(y_k)\})\) 特别地，定义整个有向图G的SG函数为整个有向图起点s的SG函数值，即SG(G) = SG(s)。出度为0的点的SG函数值为0.

有向图游戏的和

假设$G_1,G_2,G_3…,G_m$是$m$个有向图游戏，定义有向图游戏G，它的行动规划是任选某个有向图游戏$G_i$,并在$G_i$上行动一步。G被称为有向图游戏$G_1,G_2,G_3..G_m$的和，有向图游戏的和的SG函数值等于它包含的各个子游戏SG的函数值的异或和。 \(SG(G)=SG(G_1)\ xor\ SG(G_2)\ xor\ ...xor\ SG(G_m)\)

几个很重要的定理

有向图的某个局面必胜，当且仅当该局面对应节点的SG函数值大于0. 有向图游戏的某个局面必败，当且仅当该局面对应节点的SG函数值等于0. 证明：略。(太难了，我的智商不够)

Reference: A detailed blog