我只是一只蒟蒻搬运工，参考大佬课件和一下博客
https://www.cnblogs.com/wangtianxj/archive/2008/11/01/1324248.html
https://www.cnblogs.com/ww3113306/p/10281575.html
https://www.cnblogs.com/nanjoqin/p/10211576.html
https://www.cnblogs.com/zjp-shadow/p/10507030.html
https://blog.csdn.net/qq1169091731/article/details/51942752
https://blog.bill.moe/Codeforces-round460-div2-F-Game/
https://www.cnblogs.com/zwfymqz/p/8469862.html
公平组合博弈(ICG)定义：
（1）只有两人参与。
（2）游戏局面的状态集合是有限。
（3）对于同一个局面，两个游戏者的可操作集合完全相同。
（4）游戏者轮流进行游戏。
（5）当无法进行操作时游戏结束，此时不能进行操作的一方算输。
（6）无论游戏如何进行，总可以在有限步数之内结束。
局势：
P代表Previous，N代表Next。
上一次move的人有必胜策略的局面是P-position，也就是“先手必败”（奇异局势），
现在轮到move的人有必胜策略的局面是N-position,也就是“先手可保证必胜”(非奇异局势）。
（1）.无法进行任何移动的局面（也就是terminal position）是P-position；
（2）.可以移动到P-position的局面是N-position；
（3）.所有移动都导致N-position的局面是P-position。
ICG的转化：
给定一个有向无环图和一个起始顶点上的一枚棋子，两名选手交替的将这枚棋子沿有向边进行移动，无法移动者判负。
其实，任何一个ICG都可以通过把每个局势看成一个顶点，对每个局势和它的子局势连一条有向边来抽象成这个“有向图游戏”
一个性质：ICG不存在平局
可以移动到P-position的局面是N-position；所有移动都导致N-position的局面是P-position。
假设存在一种状态为平局。根据定义，平局的后继局面不存在P-position，也不都是N-position，那么平局的后继必然存在平局。
对于某个平局，不断地移动到其后继的某个平局中，由于ICG总能在有限步内结束，因此这样的移动最终在有限步后会到达terminal-position——P-position。也就是说，某个平局的后继局面中存在P-position。这样就与平局的特点产生了矛盾，因此平局不存在。
推论：有环存在 => 平局存在
一般平局存在的情况即不是ICG博弈，不保证一定能在有限步内结束游戏。我们已经知道平局的后继一定是平局，那么如果无环的话就意味着平局各不相同，有无限种可能，因此平局存在就意味着有环存在（自环也可）。
下面是三个最简单的模型：
Bash Game：只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。最后取光者得胜。
显然，如果n=m+1，那么由于一次最多只能取m个，所以，无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜。因此我们发现了如何取胜的法则：如果n=（m+1）r+s，（r为任意自然数，s≤m),那么先取者要拿走s个物品，如果后取者拿走k（≤m)个，那么先取者再拿走m+1-k个，结果剩下（m+1）（r-1）个，以后保持这样的取法，那么先取者肯定获胜。总之，要保持给对手留下（m+1）的倍数，就能最后获胜。
Wythoff Game：有两堆各若干个物品，两个人轮流从某一堆或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。
这种情况下是颇为复杂的。我们用（ak，bk）（ak ≤ bk ,k=0，1，2，...,n)表示两堆物品的数量并称其为局势，如果甲面对（0，0），那么甲已经输了，这种局势我们称为奇异局势。前几个奇异局势是：（0，0）、（1，2）、（3，5）、（4，7）、（6，10）、（8，13）、（9，15）、（11，18）、（12，20）。
可以看出,a0=b0=0,ak是未在前面出现过的最小自然数,而 bk=ak+k，奇异局势有如下三条性质：
1、任何自然数都包含在一个且仅有一个奇异局势中。
由于ak是未在前面出现过的最小自然数，所以有ak > ak-1 ，而 bk= ak + k > ak-1 + k-1 = bk-1 > ak-1 。所以性质1。成立。
2、任意操作都可将奇异局势变为非奇异局势。
事实上，若只改变奇异局势（ak，bk）的某一个分量，那么另一个分量不可能在其他奇异局势中，所以必然是非奇异局势。如果使（ak，bk）的两个分量同时减少，则由于其差不变，且不可能是其他奇异局势的差，因此也是非奇异局势。
3、采用适当的方法，可以将非奇异局势变为奇异局势
假设面对的局势是（a,b），
1).若 b = a，则同时从两堆中取走 a 个物体，就变为了奇异局势（0，0）；
2).如果a = ak ，b > bk，那么，取走b - bk个物体，即变为奇异局势；
3).如果a = ak，b < bk ,则同时从两堆中拿走ak-ab-ak个物体,变为奇异局势（ab-ak, ab - ak+ b - ak）；
4).如果a > ak ，b= ak + k,则从第一堆中拿走多余的数量a - ak 即可；
5).如果a < ak ，b= ak + k,分两种情况，
第一种，a=aj （j < k）,从第二堆里面拿走 b - bj 即可；
第二种，a=bj （j < k）,从第二堆里面拿走 b - aj 即可；
从如上性质可知，两个人如果都采用正确操作，那么面对非奇异局势，先拿者必胜；反之，则后拿者取胜。
那么任给一个局势（a，b），怎样判断它是不是奇异局势呢？我们有如下公式：
ak =[(1+√5)/2]k，bk= ak + k=[(3+√5)/2]k（k=0，1，2，...,n 方括号表示取整函数）
即对于给定的(a,b)，若[(1+√5)/2](a-b)=a，则为奇异局势
证明：
Betty定理：对于任意满足1/a+1/b=1,的正无理数a，b，都有结论：[a]，[2a]，[3a]，[4a]......[b]，[2b]，[3b]，[4b]......都是不同的数，而且覆盖正整数集。
证明：对于任意正整数n，考虑[a]，[2a]，[3a]，[4a]......里面有多少个数小于n
已知 [ka]<n 当且仅当 ka<n 即，k<n/a （k为整数）
因为n/a是无理数，所以上式还等价于k<=[n/a]
所以说，[a]，[2a]，[3a]，[4a]......里面有[n/a]个数小于n
同理，[b]，[2b]，[3b]，[4b]......里面有[n/b]个数小于n
又因为1/a+1/b=1, 所以n/a+n/b=n，且n/a和n/b都是无理数，所以[n/a]+[n/b]=n-1
所以说，对于任意正整数n，[a]，[2a]，[3a]，[4a]......[b]，[2b]，[3b]，[4b]......中有n-1个数小于n
由此，可以利用数学归纳法推出betty贝蒂定理。
简述如下：
考虑[a]，[2a]，[3a]，[4a]......[b]，[2b]，[3b]，[4b]......中每个正整数有多少个
有1个数小于2，所以有1个1
有2个数小于3，所以有1个2
有3个数小于4，所以有1个3
......
就这样，利用数学归纳法，可以得到每个正整数都有且仅有1个。
并且, 对于a、b, 如果a=b-1, 则[ka]=[kb]-k
假设存在这样的a、b, 即有方程组
1/a+1/b=1 => ( ka , kb )中每个正整数出现且仅出现一次
a=b-1 （这就是奇异局势的性质一啊）
ak =[(1+√5)/2]k，bk= ak + k=[(3+√5)/2]k
因此，这样的(ak,bk)就是所有的奇异局势（k从0开始的话，(0,0)也就算在里面了）
Nimm Game: 有三堆各若干个物品，两个人轮流从某一堆取任意多的物品，规定每次至少取一个，多者不限，最后取光者得胜。
奇异局势： （0，0，0）
（0，1，1），（1，2，3）
可看出以下三条性质：
1.（a，b，c）为奇异局势 ó a ^ b ^ c=0
2.任意操作都能将奇异局势变成非奇异局势
3.总有操作可以将非奇异局势变成奇异局势
证明：
设满足（a，b，c）：a^b^c=0 的局势为p局势
对于一个p（a，b，c），有a^b^c=0，任意改变abc中的一个数，则总体的异或结果发生改变，即不为0。因此任意操作能将p局势变成非p局势。
对于一个非p局势（a，b，c），有a^b^c=x>0，设x的二进制中最高的1在第k位，则abc中一定存在一个二进制第k位为1的数m，且m xor x<m，所以将m变成m xor x，又由于异或满足交换律，因此改变后的异或和可写成a^b^c^x，这个式子的结果一定为0。因此一定存在操作能将非p局势变为p局势。
已知（0，0，0）为p局势，根据第二条，任何其他的p局势不能一次操作就变成（0，0，0），只有某些非p局势才能进行一次操作后变成（0，0，0）；由于（a，b，c）中abc是在一直减少的，一定会在某一步到达（0，0，0），因此如果面对非p局势的选手总将当前的非p局势变成p局势，那么面对p局势的选手将一直面对p局势，直到最终面对（0，0，0）这一p局势。
也就是说，只要面对非p局势的选手总将非p局势变成p局势，面对p局势的选手必败。
因此，p局势即为奇异局势。
按照这种理论，nim博弈还可以进行延伸：有n堆各若干个物品，两个人轮流从某一堆取任意多的物品，规定每次至少取一个，最后取光者获胜。
设某一局势为（x1，x2，x3...，xn），那么满足x1^x2^x3 ...^xn =0的局势为奇异局势。
奇异局势的性质与开始的问题完全一致，证明方法也完全一样。
由Nim Game我们可以推广出SG函数：
SG游戏：公平的无法操作的一方算输
mex(minimal excludant)运算：这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数。例如mex{0,1,2,4}=3、mex{2,3,5}=0。特别的，mex{}=0。
SG函数：对于任意状态 x ， 定义 SG(x) = mex(S),其中 S 是 x 后继状态的SG函数值的集合。如 x 有三个后继状态分别为 SG(a),SG(b),SG(c)，那么SG(x) = mex{SG(a),SG(b),SG(c)}。
性质：
- 1. sg值为0的状态为P状态，sg不为0的状态为N状态。
由sg函数定义易证：terminal-position的sg值为0，为P状态；
由定义易得（参考前面Nim游戏的性质）1)sg值为0的状态后继状态sg值都不为0
2)sg值不为0的状态后继状态一定存在sg值为0的状态。
- 2. 对于某个N状态，设其sg值为x，则其后继状态中存在所有sg值0到x-1的状态。
（一定没有sg值为x的后继状态，但是可能有大于x的后继状态）
根据定义定义 SG(x) = mex(S),其中 S 是 x 后继状态的SG函数值的集合。易得
因此我们可以将这类有向图博弈都类比（注意是类比不一样）为1维Nim游戏：
Nim游戏：只有一堆石子数量为K，可以把石子数量变成0到K-1
SG函数：当前SG函数值为下，通过一次操作得到的后继SG函数值可以为0到x-1
（当然Nim游戏SG只能递减）
由此处，假如我们面对这样的问题：
对于有向无环图，n个起点处有棋子，两个人轮流移动一个棋子一步，谁无法移动就失败。
那么每一个棋子的状态都可以用sg值来描述，也就是说n个棋子就可以等同于n维Nim游戏。（并不是完全等同，因为sg函数可以增加）
SG定理：n个游戏的某个状态的sg值等于每个游戏状态sg值的异或和。
就是说，上述的一图多棋子游戏，或者干脆是Nim游戏，它的状态如果是（sg1 sg2 ... sgn），那么整个抽象成一棋子游戏或者一维Nim游戏的话（因为它也是ICG游戏），这个状态的sg值为 sg1^sg2 ...^sgn。
- SG(x) = mex(S)，而mex(S)又是最小的不属于S集合的非负整数。
- 因此我们先将异或和记作k，设当前状态为（sg1 sg2 ... sgn），则只须证明两点：
- 1.当前状态的k为后继状态k中未出现的值。
- 2.当前状态的k为后继状态k中未出现的值中的最小值。
- 1：将（sg1 sg2 ... sgn）中的任一个值改变，则k值一定改变，因此后继状态中一定不会出现当前k值。
- 2：即证改变（sg1 sg2 ... sgn）中的一个值可以将k变成任一个小于当前的非负整数。我们对k的二进制进行讨论，将k变小的操作就是：将某一位1变成0，然后对之前位进行随意修改，对之后位不进行修改；那么对于改成0的这一最高位，我们一定可以找到sgm使sgm的这一位为1，从而对sgm的相关位改动就可以完成对k的改动。
这样，复杂的博弈问题，如果能分解成若干个有向图游戏（ICG博弈），就能将其转化成n维Nim游戏，从而转化为1维Nim游戏进行解决。
根据SG函数的性质我们可以把SG函数和Nim游戏联想起来：
Nim游戏规则选择一堆数目为k的石子，我们可以把这堆石子的数目变为0到k-1
把n枚棋子所在点的SG值看作n堆该数量的棋子，
这个Nim游戏的每个必胜策略都对应现在这n个棋子游戏的必胜策略
解决的关键在于找到问题的sg函数定义的方式，或者说抽象成n堆石子Nim游戏的方式。
注意Nim的SG只能递减但其实SG游戏的SG并不一定递减，只是一个类比，严谨的证明在前面
在引入SG函数之后我们接着引入这些模型：
Bash Game II：两个人玩游戏，有一堆石子，事先给定一个数集 S每次仅从一堆中取且可以取的石子的数量 x∈S，无子可取者为负，问谁有必胜策略。
Anti-Nim：规则同Nim游戏，只不过是取走最后一个棋子的人输。
先手必胜当且仅当：
（1）游戏的 SG 值为 0 且 所有堆的石子数都为 1。
（2）游戏的 SG 值不为 0 且 有些堆的石子数大于 1。
当所有堆的石子数都为1时，堆数为偶数时先手必胜，sg=0。
当至少有一堆石子数大于1时，分为两种情况：
- sg为0时： 若只有一堆石子数目大于1，先手可以选择把这堆石子全部取走或取到剩一个保证后手面对奇数堆数目为1的石子 => 先手必胜 => sg一定不为0
所以此时必有至少两堆石子数目大于1，因此只能转为至少有一堆石子数大于1且sg不为0的情况。
- sg不为0时：
若只有一堆石子数目大于1，则可以转为奇数堆数目为 1的石子，先手必胜；
若有至少两堆石子数目大于1，则可以将sg转为0，就是1的情况。
因此当至少有一堆石子数大于1时，先手方最终总是可以面对2的第一种情况，从而必胜。
推广：Anti-SG：规则同SG游戏，但无法操作的人赢
Anti-SG与Anti-Nim的区别：
在anti-nim游戏中，子游戏即一维nim游戏有一个特点：sg值只能下降并且sg值为0时游戏结束。
那么对于一些其他不满足这样特点的游戏，当它们作为子游戏时，总的游戏还满足这样的规律吗？
1.sg值可以上升，sg为0时游戏结束。
满足。 若对方属于已知结论中的必败态，且对方使单一游戏的sg值上升，我方可以将sg值降回原来的值，相当于对方的操作无效，但这个单一游戏的局势是向终点靠近的，而终点sg值为0，因此总会到达sg值只能下降的状态。
2.sg值可以上升，sg为0时游戏不一定结束。
不满足。 因为结论中当我方面对sg值为0状态时，我方已经胜利，但在此条件下我方必须操作，这样就存在可能性在之后使对方面对sg为0的状态，而对于普遍的游戏我们又无法对面对的sg为0的状态的与奇偶性相关的性质进行分析，从而我方可能输。
SJ定理：对于任意一个 Anti-SG 游戏，如果我们规定当局面中所有的单一游戏的 SG 值为 0 时，游戏结束，则先手必胜当且仅当：
（1）游戏的 SG 函数为 0 且 游戏中没有单一游戏的 SG 函数大于 1；
（2）游戏的 SG 函数不为 0 且 游戏中某个单一游戏的 SG 函数大于 1；
需要证明如下3种情况：
1，所有终止局面为先手必胜.(终止局面指决策集合为空的局面,即无法决策)
2，游戏中任何一个先手必败局一定只能转移到先手必胜局。
3，游戏中的任何一个先手必胜局一定能转移到至少一个先手必败局。
情况一： 局面的SG函数为0 且 游戏中存在单一游戏的SG函数大于1.
∵当前局面的SG函数为0，又∵SG函数性质(1)
∴它所能转移到的任何一个局面的SG值不为0
∵当前局面的SG值为0且游戏中某个单一游戏的SG函数大于1.
∴当前局面中必定至少有2个单一游戏的SG函数大于1（如果只有一个可以得到一个单一游戏SG全为0的局面，即得到了一个SG为0的后继局面 => 矛盾）
又∵每次至多只能更改一个单一游戏的SG值
∴情况一能转移到的任何一个局面都满足：SG!=0 且 至少有一个单一游戏的SG值大于1
（情况三，所以任何一个后继局面先手必胜，此情况先手必败）
情况二： 局面的SG函数不为0且游戏中没有单一游戏的SG函数大于1
可以发现，当前局面一定有奇数个游戏的SG值为1，其余游戏的SG值为0.
1， 将某个单一游戏的SG值更改为大于1的数。
∵转移前没有单一游戏的SG值大于1，而转移将某个单一游戏的SG值更改为大于1的数∴转移后的局面一定有且只有一个单一游戏的SG值大于1
∴后继局面的SG值一定不为0
∴后继局面满足：SG!=0 且 有且只有一个单一游戏的SG值大于1
（情况三1，所以任何一个后继局面先手必胜，此情况先手必败）
2 将某个单一游戏的SG值更改为0或1.
∵转移是将某个SG值为0的单一游戏改成SG值为1的单一游戏，或将某个SG值为1的单一游戏改成SG值为0的单一游戏。
因为当前SG!=0，所以SG=1的单一局面一定为奇数个（因为SG=单一游戏sg的异或和）
∴转移后的局面一定是偶数个SG值为1的单一局面,且不含有SG值大于1的局面；
（这样的局面先手必胜，所以任何一个后继局面先手必胜，此情况先手必败）
综上：此情况先手必败
情况三： 局面的SG函数不为0且游戏中某个单一游戏的SG函数大于1.
- 局面中只有1个单一游戏的SG值大于1。
选择更改SG最大的单一游戏，可以将其更改为0或1来保证转移后的局面有且只有奇数个SG值为1的单一游戏。(同anti-nim游戏)（先手必胜）
- 局面中至少有2个单一游戏的SG值大于1。
根据SG函数性质2，总存在一种决策可以将后继局面的SG值变为0.
∵局面中至少有2个单一游戏的SG值大于1（若只有一个先手必胜SG不为0）
又∵每次最多只能改变一个单一游戏的SG值。
∴后继局面中至少有一个游戏的SG值大于1（情况一）
（后继局面存在先手必败，此局面先手必胜）
情况四： 局面的SG函数为0且游戏中没有单一游戏的SG函数大于1.
当局面中所有单一游戏的SG值为0时，游戏结束，先手必败。
否则，局面有且仅有偶数个SG值为1的单一游戏，其余游戏的SG值为0.
我们只需要将其中的某一个SG值为1的单一游戏的SG值变为0，游戏中即可出现奇数个SG值为1的单一游戏，到达先手必败态
（后继局面存在先手必败，此局面先手必胜）
Multi-sg：有n堆石子，两个人可以从任意一堆石子中拿任意多个石子(不能不拿)或把一堆数量不少于2石子分为两堆不为空的石子，没法拿的人失败。
同样可以用sg函数来定义局面。一堆石子是一个游戏，将一堆石子分成两堆是这个游戏的一种状态，而这两堆同样可以看做独立游戏，因此这一堆石子衍生的石子堆的总的sg值等于各个sg值的异或和，从而整个局面的sg值都可以如此定义。
Multi-SG 游戏规定，在符合拓扑原则的前提下，一个单一游戏的后继可以为多个单一游戏。
Multi-SG 其他规则与 SG 游戏相同
对于上面的特定的例子，有这样的结论：
SG= x-1（x%4=0）
x（x%4=1 or 2）
x+1（x%4=3）
Every-sg： 1.对于任意单一游戏，如果还未结束，那么就必须操作。
2.其他规则同SG游戏。
需要尽早把能输的都输光，只留下必胜的游戏。那么要让必胜的游戏持续的轮数更多、让必败的游戏持续的轮数更少。
对每个单一游戏，我们可以定义函数step(x)为最优步数，即：
那么当step的最大值为奇数时先手必胜。