大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

        博弈论这个环节特别好玩，游戏嘛（不会的话做题就不好玩了，当年打比赛比赛结束后两三分钟才推出来，一看答案想撕草稿纸）

        本篇文章含有大量逻辑证明，做题用不到，不想看的可以略过直接看结论和模板

参考文献

特别鸣谢孙大佬的PPT和精彩讲解

威佐夫博弈

尼姆博弈

SG函数

斐波那契博弈

区间最值查询

ST表详解

预处理

 

 

 

 查询

巴什博弈

• 问题模型

        只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个，最后取光者得胜。

• 解决思路

        当n=m+1时，由于一次最多只能取m个，所以无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜，所以当一方面对的局势是n%(m+1)=0时，其面临的是必败的局势。所以当n=（m+1)*r+s，（r为任意自然数，s≤m)时,如果先取者要拿走s个物品，如果后取者拿走x（≤m)个，那么先取者再拿走m+1-x个，结果剩下（m+1）*（r-1）个，以后保持这样的取法，那么先取者肯定获胜。总之，要保持给对手留下（m+1）的倍数，就能最后获胜。

• 结论

        当n%(m+1)=0时，在最优策略下，后手必胜。

• 变形

        最后取光的人输 

• 结论

         当n%(m+1)=1 时，在最优策略下，后手必胜。

威佐夫博弈

• 问题模型

        有两堆各若干个物品，两个人轮流从某一堆或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。

• 模拟

        首先我们来从最简单的情况开始分析：

        如果现在的局势是(0，0)，很明显此时已经没有办法再取了，所以肯定是之前的人在上一局中取完了。

        假设现在的局势是(1，2)，那么先手只有四种取法。

        （1） 如果先手取走“1”中的1个，那么后手就从“2”中取出2个，此时取完，所以后手胜利。

        （2）如果先手取走“2”中的2个，那么后手取走“1”中的1个，此时取完，后手胜利。

        （3）如果先手取走“2”中的1个，那么后手就在两堆中各取走1个，此时取完，后手胜利。

        （4）如果先手在“1”和“2”各取走了1个，那么后手取走“2”中的1个，此时取完，后手胜利。

        由此可得，先手必输。

        假设现在的局势是（3，5），首先根据上面分析的经验，我们知道先手肯定不能把任意一堆物品取完，这是因为每次可以从任意一堆取走任意个物品，那么后手就可以直接把另一堆取完，所以后手获胜。

        所以我们这里就不分析那些情况，来分析其他的情况。

        先看在一堆中取的情况：

        （1） 假设先手在“3”中取1个，后手就可以在“5”中取走4个，这样就变成了（1，2）的局势，根据上面的分析，我们知道是先手输，后手获胜。

        （2） 假设先手在“3”中取2个，后手就可以在 “5” 中取走3个，这样也变成了（1,2）的局势了，还是先手输，后手获胜。

        （3）假设先手在“5”中取1个，后手就在 “3”和“5” 中各取走2个，这样又成了（1，2）的局势了，先手输，后手赢。

        （4）假设先手在“5”中取2个，后手就在 “3”和“5” 中各取走3个，这样变成了（0，0）的局势，先手输，后手赢。

        （5）假设先手在“5”中取3个，后手就在 “3”和“5” 中各取走1个，也变成了（1，2）的局势，先手输，后手胜利。

        （6）假设先手在“5”中取4个，后手在“3”中取走1个，还是（1，2）的局势，先手输，后手赢。

        我们发现上面列举的这几种局势，无论先手怎么取都是后手赢。

• 分析

我们可以来找找那些先手必输局势的规律

第一种（0，0）

第二种（1，2）

第三种（3，5）

第四种  (4 ，7）

第五种（6，10）

第六种  (8，13）

第七种  (9 ， 15）

第八种  (11 ，18）

第n种  （a[k]，b[k]）

我们把这些局势称为“奇异局势”

我们会发现他们的差值是递增的，分别是0,1,2,3,4,5,6,7……n

有兴趣的读者可以自己模拟一下过程进行验证

我们用数学方法分析发现这些局势的第一个值是未在前面出现过的最小的自然数。

继续分析我们会发现，每种奇异局势的第一个值(这里假设第一堆数目小于第二堆的数目)总是等于当前局势的差值乘上1.618

我们都知道0.618是黄金分割率。而威佐夫博弈正好是1.618，这就是博弈的奇妙之处！

即 a[k] = (int)  （(b[k] – a[k])*1.618） 注：这里的int是强制类型转换，注意这不是简单的四舍五入，假如后面的值是3.9，转换以后得到的不是4而是3，也就是说强制int类型转换得到的是不大于这个数值的最大整数。

在编程题中，有些题目要求精度较高，我们可以用下述式子来表示这个值

1.618 = (sqrt(5.0) + 1) / 2

• 性质

任何自然数都包含在一个且仅有一个奇异局势中

任意操作都可将奇异局势变为非奇异局势

采用适当的方法，可以将非奇异局势变为奇异局势

• 结论

        由上述性质可知，如果双方都采取正确操作，那么面对非奇异局势，先取者必胜；反之，面对奇异局势，后取者必胜。

• 例题

POJ1067

        有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。

        游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。

        现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。

        输入包含若干行，表示若干种石子的初始情况，其中每一行包含两个非负整数a和b，表示两堆石子的数目，a和b都不大于1,000,000,000。

        输出对应也有若干行，每行包含一个数字1或0，如果最后你是胜者，则为1，反之，则为0。

尼姆博弈

• 问题模型

        有N堆石子。A B两个人轮流拿，A先拿。每次只能从一堆中取若干个，可将一堆全取走，但不可不取，拿到最后1颗石子的人获胜。假设A B都非常聪明，拿石子的过程中不会出现失误。给出N及每堆石子的数量，问最后谁能赢得比赛。

• 分析 

        以N=3为例 与二进制有关系，我们用（a，b，c）表示某种局势，首先（0，0，0）显然是奇异局势，无论谁面对奇异局势，都必然失败。第二种奇异局势是（0，n，n），只要与对手拿走一样多的物品，最后都将导致（0，0，0）。仔细分析一下，（1，2，3）也是奇异局势，无论对手如何拿，接下来都可以变为（0，n，n）的情形。 规律：当a^b^c = 0时，此局势为奇异局势（对任意N成立）。

• 推导

       我们这里简化一下，假设只有两堆石子。那么，当两堆石子数量相等的时候，我们的A同志是必败的。

       很好！我们已经找到了一个非常关键的规律：当两堆石子数量相等的时候，先手必输！

       那么我们再来想这么一个问题，假设存在有第三堆石子，前两堆石子的数量相同，最后一堆石子数量不同，比如1，1，3，我们看一下，此时A同志又可以必赢，这是为什么呢？我们可以发现，第三堆石子A可以直接拿走，转化成了B先手，两堆石子数量一样的情况。

       那么如果是1，1，1的情况呢？你很容易发现A其实必赢。

       好了，情况列举就到这里，接下来我们要开始进行推导了。

       由【任意两堆数量相同的石子博弈情况为先手必输】再加上1，1，1情况先手必赢，我们开始进行总结。

       我们在取第三堆石子的时候要考虑到前两堆石子的输赢情况，当然这里取石子的方法，顺序我们并不能决定，我们只是计算有没有必赢的情况。

       现在！一个大佬要把这个东西和二进制联系到一起了！

       我们知道，石子的数量肯定是非负整数，那就肯定有其二进制表示！

       比如两堆石子数量分别为7和5

       二进制分别为：111和101。那么7就可以看作为4+2+1，5可以看作为4+1。对！二进制拆分！

       111=100+10+1，101=100+1。

       换成十进制就是：

       7=4+2+1，5=4+1。

       现在！石子的堆数变了！不是两堆！是五堆石子！其中两堆的数量为4，两堆为1，这两堆里先手可以必输，然后最后一堆数量不管多少直接拿走取得胜利！

       至此就解释了为什么这个东西可以和二进制联系在一起。

       那么再解释一下这个鬼东西为什么要和二进制联系在一起。因为我们看到上述变形里面我们知道了数量为4和1的那几堆使得先手在那里必输，那么我们可不可以在二进制运算里面把他们直接归零不计呢？

       对！可以！用异或就很简单！而且在C语言里面可以直接写出来异或运算！方便快捷还省事儿！而且人家直接就是按照二进制去算的！这一步就直接把转换二进制什么的全给做完了。

       按照上述例子，7和5，异或计算过后答案是2。答案是2！这个2何其熟悉！如果两个数字相同异或结果为0的话，先手必输。反之不为0就先手可以必赢。0为假非0为真！而且异或后的结果是什么呢？是去除了所有二进制拆分后数量相等的石子堆之后还剩余的石子。

       下面我们再来扩展一下，n堆石子的情况。

       假设n为3，三堆石子数量分别为a，b，c。如果我们a^b==0那么c只要不为0的话A就可必赢，因为前面A可以必输。后面A就可以躺赢。所以，如果a^b^c!=0，A就可以必赢。为什么呢？我们把ab合成一堆去看，会发现这时问题简化成为了两堆石子。两堆石子！也就说两堆石子只要数量不同就可以！

       同理，n=1,2,3,4,5…都可以。只要a^b^c^d^…….!=0，那么A就可必赢！

• 结论

        一个必败局面(奇异局势)无论做出何种操作，最终结果都是输的局面。必败局面经过2次操作后，可以达到另一个必败局面。一个必胜局面(非奇异局势)经过1次操作后一定可以达到必败局面(奇异局势)。

        所有物品数目二进制异或结果为0，此时为必败局面(奇异局势)，则先手必输。

        所有物品数目二进制异或不为0，此时为必胜局面(非奇异局势)，一次操作后一定可以转为必败局面，则后手必输。

• 奇异局势与非奇异局势转换

        注意到异或运算的交换律和结合律，即a^a=0，有: a ^ b ^ ( a ^ b ) = ( a ^ a ) ^ ( b ^ b ) = 0 ^ 0 = 0.

        所以对于局势(a,b,c)(假设a<=b<=c） 我们只需把c变为a^b即可变为奇异局势，即从c中拿走 c-(a^b)。

        一定要用较大的数作为c，保证有石子可拿。

        具体用哪个视情况而定。

• 例题

洛谷1247

 

斐波那契博弈

• 问题模型

有一堆个数为n的石子，游戏双方轮流取石子，满足：

（1）先手不能在第一次把所有的石子取完；

（2）之后每次可以取的石子数介于1到对手刚取的石子数的2倍之间（包含1和对手刚取的石子数的2倍）。

约定取走最后一个石子的人为赢家。

• 结论

当n为Fibonacci数时，先手必败。即存在先手的必败态当且仅当石头个数为Fibonacci数。

•  证明

用第二数学归纳法证明：

为了方便，我们将n记为f[i]。

1、当i=2时，先手只能取1颗，显然必败，结论成立。

2、假设当i<=k时，结论成立。

     则当i=k+1时，f[i] = f[k]+f[k-1]。

     则我们可以把这一堆石子看成两堆，简称k堆和k-1堆。

    （一定可以看成两堆，因为假如先手第一次取的石子数大于或等于f[k-1]，则后手可以直接取完f[k]，因为f[k] < 2*f[k-1]）

     对于k-1堆，由假设可知，不论先手怎样取，后手总能取到最后一颗。下面我们分析一下后手最后取的石子数x的情况。

     如果先手第一次取的石子数y>=f[k-1]/3，则这小堆所剩的石子数小于2y，即后手可以直接取完，此时x=f[k-1]-y，则x<=2/3*f[k-1]。

     我们来比较一下2/3*f[k-1]与1/2*f[k]的大小。即4*f[k-1]与3*f[k]的大小，对两值作差后不难得出，后者大。

     所以我们得到，x<1/2*f[k]。

     即后手取完k-1堆后，先手不能一下取完k堆，所以游戏规则没有改变，则由假设可知，对于k堆，后手仍能取到最后一颗，所以后手必胜。

     即i=k+1时，结论依然成立。

那么，当n不是Fibonacci数的时候，情况又是怎样的呢？

这里需要借助“Zeckendorf定理”（齐肯多夫定理）：任何正整数可以表示为若干个不连续的Fibonacci数之和。

关于这个定理的证明，感兴趣的同学可以在网上搜索相关资料，这里不再详述。

分解的时候，要取尽量大的Fibonacci数。

比如分解85：85在55和89之间，于是可以写成85=55+30，然后继续分解30,30在21和34之间，所以可以写成30=21+9，

依此类推，最后分解成85=55+21+8+1。

则我们可以把n写成  n = f[a1]+f[a2]+……+f[ap]。（a1>a2>……>ap）

我们令先手先取完f[ap]，即最小的这一堆。由于各个f之间不连续，则a(p-1) > ap  + 1，则有f[a(p-1)] > 2*f[ap]。即后手只能取f[a(p-1)]这一堆，且不能一次取完。

此时后手相当于面临这个子游戏（只有f[a(p-1)]这一堆石子，且后手先取）的必败态，即先手一定可以取到这一堆的最后一颗石子。

同理可知，对于以后的每一堆，先手都可以取到这一堆的最后一颗石子，从而获得游戏的胜利。
 

NIM游戏

Nim游戏是一种两个人玩的回合制数学战略游戏，它之所以经典是因为Sprague和Grundy独立地证明了一切ICG都可以化规到Nim游戏，这一类游戏都具有以下的特点：

• 玩家只有两个人
• 游戏给定了状态之间转移的规则
• 玩家的状态有限 .
• 每个人轮流移动
• 有明确的状态结束情况

游戏状态定义

• P-position代表会使上一个移动的玩家赢的状态。(必败点)
• N-position代表会使当前正在移动的玩家赢的状态。(必胜点)

游戏状态间转移的规则

• 结局状态为P-position状态
• 能到达P-position状态的状态的都是N-position状态
• 只能到达N-position状态的是P-position状态
• 当玩家面临P-position局面是必输的，当玩家面临N-position局面是必胜的

下面的逻辑推理不想看的可以略过

        

重点结论：对于一个Nim游戏的局面(a1,a2,…,an)，它是P-position当且仅当a1^a2^…^an=0，其中^表示位异或(xor)运算。
Nim游戏是博弈论中最经典的模型（之一？），它又有着十分简单的规则和无比优美的结论，由这个游戏开始了解博弈论恐怕是最合适不过了。

Nim游戏是组合游戏(Combinatorial Games)的一种，准确来说，属于“Impartial Combinatorial Games”（以下简称ICG）。满足以下条件的游戏是ICG（可能不太严谨）：1、有两名选手；2、两名选手交替对游戏进行移动(move)，每次一步，选手可以在（一般而言）有限的合法移动集合中任选一种进行移动；3、对于游戏的任何一种可能的局面，合法的移动集合只取决于这个局面本身，不取决于轮到哪名选手操作、以前的任何操作、骰子的点数或者其它什么因素； 4、如果轮到某名选手移动，且这个局面的合法的移动集合为空（也就是说此时无法进行移动），则这名选手负。根据这个定义，很多日常的游戏并非ICG。例如象棋就不满足条件3，因为红方只能移动红子，黑方只能移动黑子，合法的移动集合取决于轮到哪名选手操作。

通常的Nim游戏的定义是这样的：有若干堆石子，每堆石子的数量都是有限的，合法的移动是“选择一堆石子并拿走若干颗（不能不拿）”，如果轮到某个人时所有的石子堆都已经被拿空了，则判负（因为他此刻没有任何合法的移动）。

这游戏看上去有点复杂，先从简单情况开始研究吧。如果轮到你的时候，只剩下一堆石子，那么此时的必胜策略肯定是把这堆石子全部拿完一颗也不给对手剩，然后对手就输了。如果剩下两堆不相等的石子，必胜策略是通过取多的一堆的石子将两堆石子变得相等，以后如果对手在某一堆里拿若干颗，你就可以在另一堆中拿同样多的颗数，直至胜利。如果你面对的是两堆相等的石子，那么此时你是没有任何必胜策略的，反而对手可以遵循上面的策略保证必胜。如果是三堆石子……好像已经很难分析了，看来我们必须要借助一些其它好用的（最好是程式化的）分析方法了，或者说，我们最好能够设计出一种在有必胜策略时就能找到必胜策略的算法。

定义P-position和N-position，其中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。

按照这个定义，如果局面不可能重现，或者说positions的集合可以进行拓扑排序，那么每个position或者是P-position或者是N-position，而且可以通过定义计算出来。

以Nim游戏为例来进行一下计算。比如说我刚才说当只有两堆石子且两堆石子数量相等时后手有必胜策略，也就是这是一个P-position，下面我们依靠定义证明一下(3,3)是一个P是一个P是一个P-position。首先(3,3)的子局面（也就是通过合法移动可以导致的局面）有(0,3)(1,3)(2,3)（显然交换石子堆的位置不影响其性质，所以把(x,y)和(y,x)看成同一种局面），只需要计算出这三种局面的性质就可以了。 (0,3)的子局面有(0,0)、(0,1)、(0,2)，其中(0,0)显然是P-position，所以(0,3)是N-position（只要找到一个是P-position的子局面就能说明是N-position）。(1,3)的后继中(1,1)是P-position（因为(1,1)的唯一子局面(0,1)是N-position），所以(1,3)也是N-position。同样可以证明(2,3)是N-position。所以(3,3)的所有子局面都是N-position，它就是P-position。通过一点简单的数学归纳，可以严格的证明“有两堆石子时的局面是P-position当且仅当这两堆石子的数目相等”。

根据上面这个过程，可以得到一个递归的算法——对于当前的局面，递归计算它的所有子局面的性质，如果存在某个子局面是P-position，那么向这个子局面的移动就是必胜策略。当然，可能你已经敏锐地看出有大量的重叠子问题，所以可以用DP或者记忆化搜索的方法以提高效率（简单的博弈问题想到这一步就可以了）。但问题是，利用这个算法，对于某个Nim游戏的局面(a1,a2,…,an)来说，要想判断它的性质以及找出必胜策略，需要计算O(a1*a2*…*an)个局面的性质，不管怎样记忆化都无法降低这个时间复杂度。所以我们需要更高效的判断Nim游戏的局面的性质的方法。

直接说结论好了。(Bouton’sTheorem)对于一个Nim游戏的局面(a1,a2,…,an)，它是P-position当且仅当a1^a2^…^an=0，其中^表示异或(xor)运算。怎么样，是不是很神奇？我看到它的时候也觉得很神奇，完全没有道理的和异或运算扯上了关系。但这个定理的证明却也不复杂，基本上就是按照两种position的证明来的。

根据定义，证明一种判断position的性质的方法的正确性，只需证明三个命题： 1、这个判断将所有terminal position判为P-position；2、根据这个判断被判为N-position的局面一定可以移动到某个P-position；3、根据这个判断被判为P-position的局面无法移动到某个P-position。

第一个命题显然，terminalposition只有一个，就是全0，异或仍然是0。

第二个命题，对于某个局面(a1,a2,…,an)，若a1^a2^…^an!=0，一定存在某个合法的移动，将ai改变成ai’后满足a1^a2^…^ai’^…^an=0。不妨设a1^a2^…^an=k，则一定存在某个ai，它的二进制表示在k的最高位上是1（否则k的最高位那个1是怎么得到的）。这时ai^k<ai一定成立。则我们可以将ai改变成ai’=ai^k，此时a1^a2^…^ai’^…^an=a1^a2^…^an^k=0。

第三个命题，对于某个局面(a1,a2,…,an)，若a1^a2^…^an=0，一定不存在某个合法的移动，将ai改变成ai’后满足a1^a2^…^ai’^…^an=0。因为异或运算满足消去率，由a1^a2^…^an=a1^a2^…^ai’^…^an可以得到ai=ai’。所以将ai改变成ai’不是一个合法的移动。证毕。

根据这个定理，我们可以在O(n)的时间内判断一个Nim的局面的性质，且如果它是N-position，也可以在O(n)的时间内找到所有的必胜策略。Nim问题就这样基本上完美的解决了。
 

公平组合博弈（ICG）

•  定义

（1）两人参与。

（2）游戏局面的状态集合是有限。

（3）对于同一个局面，两个游戏者的可操作集合完全相同

（4）游戏者轮流进行游戏。

（5）当无法进行操作时游戏结束，此时不能进行操作的一方算输。

（6）无论游戏如何进行，总可以在有限步数之内结束。

• 内容

包括以上博弈，是更根本一级的抽象

• 解决思路

P状态：必败点；

N状态：必胜点。

假定我们给出两个游戏G1 和 G2。如果我们只知道单个游戏的P-状态和N-状态我们能够正确地玩好游戏和G1 + G2吗？

        答案是否定的。不难看出两个P-状态的和总是P-状态，P-状态和N-状态的和总是N-状态。但是两个N-状态的和既可能是P-状态也可能是N-状态。因此，只知道单个游戏的P-状态和N-状态是不够的。 为了正确地玩好游戏和我们需要推广P-状态和N-状态，它就是Sprague-Grudy函数（或者简称为sg函数）。

SG函数

• 总述

        打出SG表后判断当前状态SG值为0还是非0就行，0就是必败点，输，非0就是赢，模板比较固定，用途比较万能。

• ICG抽象模型

        给定一个有向无环图和一个起始顶点上的一枚棋子，两名选手交替的将这枚棋子沿有向边进行移动，无法移动者判负。 这个游戏可以认为是所有ICG的抽象模型。

        也就是说，任何一个ICG都可以通过把每个局面看成一个顶点，对每个局面和它的子局面连一条有向边来抽象成这个“有向图游戏”。 必胜点（N）与必败点（P） 所有终结点是 必败点 P 。（我们以此为基本前提进行推理） 从任何必胜点N 操作，至少有一种方式可以进入必败点 P。 无论如何操作，必败点P 都只能进入 必胜点 N。

• SG定理

游戏和的SG函数等于各个游戏SG函数的Nim和（各个数相异或的结果）。

        对于ICG游戏，我们可以将游戏中每一个可能发生的局面表示为一个点。并且若存在局面i和局面j，且j是i的后继局面(即局面i可以转化为局面j)，我们用一条有向边，从i出发到j，连接表示局面i和局面j的点。则整个游戏可以表示成为一个有向无环图：

        根据ICG游戏的定义我们知道，任意一个无法继续进行下去的局面为终结局面，即P局面(先手必败)。

        在图中我们可以标记所有出度为0的点为P点（P点不一定出度为0，充分不必要）。接着根据ICG游戏的两条性质，我们可以逆推出所有点为P局面还是N局面：

• 必胜点（N）与必败点（P） 所有终结点是 必败点 P 。（我们以此为基本前提进行推理）
• 从任何必胜点N 操作，至少有一种方式可以进入必败点 P。
• 无论如何操作，必败点P 都只能进入 必胜点 N。

 

 

因此，对于任意一个ICG游戏，我们可以采取逆推的方法，标记出所有局面是N局面还是P局面。 但仅仅只是标记N、P，所能得到的信息太少，于是我们定义了Sg(Sprague-Grundy)函数：

对于一个游戏可能发生的局面x，我们如下定义它的sg值：

(1)若当前局面x为终结局面，则sg值为0。

(2)若当前局面x非终结局面，其sg值为： sg(x) = mex{sg(y) | y是x的后继局面}。

mex{a[i]}表示a中未出现的最小非负整数。举个例子来说：

mex{0, 1, 2} = 3

mex{1, 2}=0

mex{0,1,3}=2

我们将上图用sg函数表示后，得到：

对于任意状态的x,定义SG(x)=mex(S),其中S是x后继状态的SG函数值的集合，一般情况下我们会开一个S[]数组，其中他的下标表示在当前for循环下，取过一次之后后继状态的SG函数值。可以通过将这些后继状态得到的SG函数值全部标记，然后后继遍历S[]数组，找出最小的未被标记的值作为找到的mex(S)

可以发现，若一个局面x为P局面，则有sg(x)=0；否则sg(x)>0。同样sg值也满足N、P之间的转换关系：

若一个局面x，其sg(x)>0，则一定存在一个后续局面y，sg(y)=0。

从任何必胜点N 操作，至少有一种方式可以进入必败点 P

若一个局面x，其sg(x)=0，则x的所有后续局面y，sg(y)>0。

无论如何操作，必败点P 都只能进入 必胜点 N

由上面的推论，我们可以知道用N、P-Position可以描述的游戏用sg同样可以描述。并且在sg函数中还有一个非常好用的定理，叫做sg定理：

对于多个单一游戏，X=x[1..n]，每一次我们只能改变其中一个单一游戏的局面。则其总局面的sg值等于这些单一游戏的sg值异或和。

即：         sg(X) = sg(x[1]) xor sg(x[2]) xor … xor sg(x[n])

        让我们再来考虑一下顶点的SG值的意义。当g(x)=k时，表明对于任意一个0<=i<k，都存在x的一个后继y满足g(y)=i。也就是说，当某枚棋子的SG值是k时，我们可以把它变成0、变成1、……、变成k-1，但绝对不能保持k不变。不知道你能不能根据这个联想到Nim游戏，Nim游戏的规则就是：每次选择一堆数量为k的石子，可以把它变成0、变成1、……、变成k-1，但绝对不能保持k不变。这表明，如果将n枚棋子所在的顶点的SG值看作n堆相应数量的石子，那么这个Nim游戏的每个必胜策略都对应于原来这n枚棋子的必胜策略！

SG值计算方法（重点）

1.可选步数为1~m的连续整数，直接取模即可，SG(x) = x % (m+1);

2.可选步数为任意步，SG(x) = x;

• 打表

SG数组是所要打表的数组

S数组是临时记录那些被标记

f数组是每次取石子的取法

N是取法的个数

n是打表的范围

 每次循环先清空临时数组S。i是当前状态，比如目前还剩多少石子。j是要改变的状态增量△，比如我要取走2颗石子。那么j要小于N，N是取法的个数，比如最多取N颗。f[j]要小于i，你不能目前只有3颗你拿走4颗。涉及到的SG[]肯定是之前循环中处理过的，类似dp。i-f[j]是改变后的状态

• DFS

//注意 S数组要按从小到大排序 SG函数要初始化为-1 对于每个集合只需初始化1遍
//n是集合s的大小 S[i]是定义的特殊取法规则的数组
int s[110],sg[10010],n;
int SG_dfs(int x)
{
    int i;
    if(sg[x]!=-1)
        return sg[x];
    bool vis[110];
    memset(vis,0,sizeof(vis));
    for(i=0;i<n;i++)
    {
        if(x>=s[i])
        {
            SG_dfs(x-s[i]);
            vis[sg[x-s[i]]]=1;
        }
    }
    int e;
    for(i=0;;i++)
        if(!vis[i])
        {
            e=i;
            break;
        }
    return sg[x]=e;
}

一般DFS只在打表解决不了的情况下用，首选打表预处理。

• 巴什博弈的SG打表 

一堆石子有n个，每次最多取m个

• 类NIM游戏的SG打表

一堆石子有n(n<=1000)个，每次取的石子是 按照斐波那契数来去取 比如取（1，2，3，5，8…)

 

• HDU-1846

https://acm.hdu.edu.cn/showproblem.php?pid=1846

解法一： 巴什博弈：

解法二： SG函数 

•  HUD 1847

解法一 巴什博弈

解法二 SG函数

 

• HDU 1848

SG定理 游戏和的SG函数等于各个游戏SG函数的Nim和（各个数相异或的结果）。