1. 巴什博奕

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

这个问题很基础。

先说结论：

• 如果 $n\text{ mod }(m+1)=0$，那么后手必胜
• 否则先手必胜

为什么呢？

首先考虑第一种情况：$n\text{ mod }(m+1)=0$

此时设先手取了 $x,x\in [1,m]$个，那么后手只要取 $m+1-x$个就行了，这样 $n\text{ mod }(m+1)=0$依然成立。

最后必然会出现剩下 $m+1$个物品，先手无法一次取完，但 Ta 必须取一个，这样后手就一定能一次取完剩下的所有的物品了。

对于第二种情况，只要先手先取 $n\text{ mod }(m+1)$个物品，这样局势就又满足了 $n\text{ mod }(m+1)=0$，而这时后手成先手了。。。因此这种情况下先手必胜啦！

模板：

#include <bits/stdc++.h>
using namespace std;
int m,n,ans;
int main()
{
    scanf("%d%d",&m,&n);//物品数为 m，上限为 n
    if(!(ans=(m%(n+1)))){printf("none\n");return 0;}//必败
        //以下是从小到大输出第一次取的物品数
    printf("%d",ans);
    for(ans+=n+1;ans<=m&&ans<=n;ans+=n+1)printf(" %d",ans);
    for(ans-=n;ans>m&&ans<=n;ans++)printf(" %d",ans);
    return 0;
}

2. 威佐夫博弈

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

首先分析一波:

设 $(a,b)$表示两堆分别有 $a$个和 $b$个物品。

因为 $(a,b)$与 $(b,a)$等价，因此不妨设 $a\leq b$。

那么：

• 对于局势 $(0,0)$，先手输，先手无必胜策略
• 对于当前局势，若能经过一次操作得到对手无不胜策略，则此时此人有必胜策略
• 对于当前局势，若无论如何操作一次，都会得到对手有必胜策略的局势，则此时此人无必胜策略

我们称先手（当前操作的人）无必胜策略的局势为 “奇异局势”。

先手动列举一下前几个奇异局势 $(a,b),a\leq b$：

$$(0,0),(1,2),(3,5),(4,7),(6,10),(8,13),(9,15),(11,18),(12,20)…$$

观察一下规律，我们欣喜地发现，第 $k$个奇异局势的 $a_k$为前 $k-1$个奇异局势中未出现的最小自然数（即该自然数不等于 $a_x$或 $b_x,x\in [1,k-1]$，且该自然数最小）。而 $b_k=a_k+k$。

这是为什么呢？

不妨把局势放到二维平面中。

对于奇异局势 $(a,b)$，$(a,b+k),(a+k,b),(a+k,b+k)$都不是奇异局势。

因此我们先在二维平面中找到第一个奇异局势——$(0,0)$，并把 $(0,k),(k,0),(k,k)$都涂黑。

涂黑的都是 “非奇异局势”，即有必胜策略的局势。

接着找到 $x,y$最小且 $x\leq y$且未被涂黑的点，发现是 $(1,2)$。那么 $(1,2)$为第二个奇异局势。

把 $(1,2+k),(1+k,2),(1+k,2+k)$都涂黑。

然后找到 $(1,2)$的对称点 $(2,1)$，显然它也是个奇异局势，但我们不用管它（因为它的 $a>b$）。我们把 $(2,1+k),(2+k,1),(2+k,1+k)$涂黑。

接着找到 $x,y$最小且 $x\leq y$且未被涂黑的点，发现是 $(3,5)$。那么 $(3,5)$为第二个奇异局势。

还是老规矩，把非奇异局势涂黑，再找到对称点，涂黑非奇异局势。。。

以此类推，就能找出所有的奇异局势了。

显然，若 $a_k$等于了 $a_x$或 $b_x,x\in [1,k-1]$，那么 $x=a_k$这一列显然都被涂黑了，与我们的推导相矛盾，所以 $a_k$必然是未出现过的最小自然数。

而 $b_k=a_k+k$我也不会证，大概是因为 $(a+k,b+k)$会被涂黑的缘故。。。（QvQ 表打我啊！）

知道了奇异局势，那么就可以轻松解决威佐夫博弈问题啦～

• 当 $a=b$时, 只要同时从两堆中取走 $a$个物体, 就变为了奇异局势 $(0,0)$
• 当 $a=a_k,b>b_k$时，只要取走 $b-b_k$个物体，就能变为奇异局势
• 当 $a=a_k,b < b_k$时，只要从两堆中拿走 $a-a _ {b-a}$个物体就能变为奇异局势
• 当 $a>a_k,b=a_k+k$时，只要从第一堆中拿走若干变成 $a_k$即可
• 当 $a < a_k,b=a_k+k$时，只要从第二堆中拿走若干，变成 $a$对应的局势即可。

请注意上面的 $a$均小于等于 $b$。

现在的问题就是如何判断当前局势是不是奇异局势了。

这里有个公式：

$$a_k=\left [ \frac{k(1+\sqrt{5})}{2}\right ] $$

（其中中括号表示取整数部分）

然后 $b_k=a_k+k$

因此我们只需要先求出 $k=a-b$，再根据 $k$判断 $a_k$是否满足上面那个公式就行了。

。。。

看了半天还是不知道这个公式是怎么推导的啊！！！

嘤嘤嘤 QvQ

算啦，那就死记硬背啦~(≧▽≦)/~啦啦啦

顺带一提，$\frac{1+\sqrt{5}}{2}\approx 1.61803398874989484820$，也就是传说中的黄金分割比。

那么公式我们只要记 $a_k=\left [ 1.618k \right ]$即可。

至此，威佐夫博弈也差不多弄完啦～

段错误，作者已放弃。

模板：

#include <bits/stdc++.h>
using namespace std;
int a,b;
int main()
{
    scanf("%d%d",&a,&b);//输入两堆物品数
    if(a>b)swap(a,b);
    if(a==floor(1.618*(b-a)))printf("0\n");//后手必胜
    else printf("1\n");//先手必胜
    return 0;
}

3. SG 函数

也就是死 GAY 函数。

它和 Nim 游戏有莫大的联系。

直接转两篇文章吧，写得很棒～我觉得没必要在重复造轮子了 QvQ

好吧我承认我偷懒了 QvQ 但是我还帮他排版了呀！表打我嘛 QvQ

原文地址：

• https://www.cnblogs.com/Knuth/archive/2009/09/05/1561008.html
• https://www.cnblogs.com/Knuth/archive/2009/09/05/1561007.html

博弈论（一）：Nim 游戏

重点结论：对于一个 Nim 游戏的局面 (a1,a2,...,an)，它是 P-position 当且仅当 a1^a2^...^an=0，其中^表示位异或 (xor) 运算。(P-position 的定义在后文会给出啦 QvQ)

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(a1a2...an)个局面的性质，不管怎样记忆化都无法降低这个时间复杂度。所以我们需要更高效的判断 Nim 游戏的局面的性质的方法。

直接说结论好了。(Bouton’s Theorem) 对于一个 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。

第一个命题显然，terminal position 只有一个，就是全 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 问题就这样基本上完美的解决了。

博弈论（二）：Sprague-Grundy 函数

上一期的文章里我们仔细研究了 Nim 游戏，并且了解了找出必胜策略的方法。但如果把 Nim 的规则略加改变，你还能很快找出必胜策略吗？

比如说：有 n 堆石子，每次可以从第 1 堆石子里取 1 颗、2 颗或 3 颗，可以从第 2 堆石子里取奇数颗，可以从第 3 堆及以后石子里取任意颗……这时看上去问题复杂了很多，但相信你如果掌握了本节的内容，类似的千变万化的问题都是不成问题的。

现在我们来研究一个看上去似乎更为一般的游戏：给定一个有向无环图和一个起始顶点上的一枚棋子，两名选手交替的将这枚棋子沿有向边进行移动，无法移动者判负。

事实上，这个游戏可以认为是所有 Impartial Combinatorial Games 的抽象模型。也就是说，任何一个 ICG 都可以通过把每个局面看成一个顶点，对每个局面和它的子局面连一条有向边来抽象成这个 “有向图游戏”。

下面我们就在有向无环图的顶点上定义 Sprague-Garundy 函数。

首先定义 mex(minimal excludant)运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数。例如 mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。

对于一个给定的有向无环图，定义关于图的每个顶点的 Sprague-Garundy 函数 g 如下：g(x)=mex{ g(y) | y 是 x 的后继 }。

来看一下 SG 函数的性质。首先，所有的 terminal position 所对应的顶点，也就是没有出边的顶点，其 SG 值为 0，因为它的后继集合是空集。然后对于一个 g(x)=0 的顶点 x，它的所有后继 y 都满足 g(y)!=0。对于一个 g(x)!=0 的顶点，必定存在一个后继 y 满足 g(y)=0。

以上这三句话表明，顶点 x 所代表的 postion 是 P-position 当且仅当 g(x)=0（跟 P-positioin/N-position 的定义的那三句话是完全对应的）。我们通过计算有向无环图的每个顶点的 SG 值，就可以对每种局面找到必胜策略了。但 SG 函数的用途远没有这样简单。如果将有向图游戏变复杂一点，比如说，有向图上并不是只有一枚棋子，而是有 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 枚棋子的必胜策略！

对于 n 个棋子，设它们对应的顶点的 SG 值分别为 (a1,a2,...,an)，再设局面 (a1,a2,...,an)时的 Nim 游戏的一种必胜策略是把 ai 变成 k，那么原游戏的一种必胜策略就是把第 i 枚棋子移动到一个 SG 值为 k 的顶点。这听上去有点过于神奇——怎么绕了一圈又回到 Nim 游戏上了。

其实我们还是只要证明这种多棋子的有向图游戏的局面是 P-position 当且仅当所有棋子所在的位置的 SG 函数的异或为 0。这个证明与上节的 Bouton’s Theorem 几乎是完全相同的，只需要适当的改几个名词就行了。

刚才，我为了使问题看上去更容易一些，认为 n 枚棋子是在一个有向图上移动。但如果不是在一个有向图上，而是每个棋子在一个有向图上，每次可以任选一个棋子（也就是任选一个有向图）进行移动，这样也不会给结论带来任何变化。

所以我们可以定义有向图游戏的和 (Sum of Graph Games)：设 G1、G2、……、Gn 是 n 个有向图游戏，定义游戏 G 是 G1、G2、……、Gn 的和 (Sum)，游戏 G 的移动规则是：任选一个子游戏 Gi 并移动上面的棋子。

Sprague-Grundy Theorem 就是：g(G)=g(G1)^g(G2)^...^g(Gn)。也就是说，游戏的和的 SG 函数值是它的所有子游戏的 SG 函数值的异或。

再考虑在本文一开头的一句话：任何一个 ICG 都可以抽象成一个有向图游戏。所以 “SG 函数” 和 “游戏的和” 的概念就不是局限于有向图游戏。

我们给每个 ICG 的每个 position 定义 SG 值，也可以定义 n 个 ICG 的和。所以说当我们面对由 n 个游戏组合成的一个游戏时，只需对于每个游戏找出求它的每个局面的 SG 值的方法，就可以把这些 SG 值全部看成 Nim 的石子堆，然后依照找 Nim 的必胜策略的方法来找这个游戏的必胜策略了！

回到本文开头的问题。

有 n 堆石子，每次可以从第 1 堆石子里取 1 颗、2 颗或 3 颗，可以从第 2 堆石子里取奇数颗，可以从第 3 堆及以后石子里取任意颗……

我们可以把它看作 3 个子游戏，第 1 个子游戏只有一堆石子，每次可以取 1、2、3 颗，很容易看出 x 颗石子的局面的 SG 值是 x%4。

第 2 个子游戏也是只有一堆石子，每次可以取奇数颗，经过简单的画图可以知道这个游戏有 x 颗石子时的 SG 值是 x%2。第 3 个游戏有 n-2 堆石子，就是一个 Nim 游戏。

对于原游戏的每个局面，把三个子游戏的 SG 值异或一下就得到了整个游戏的 SG 值，然后就可以根据这个 SG 值判断是否有必胜策略以及做出决策了。

其实看作 3 个子游戏还是保守了些，干脆看作 n 个子游戏，其中第 1、2 个子游戏如上所述，第 3 个及以后的子游戏都是 “1 堆石子，每次取几颗都可以”，称为 “任取石子游戏”，这个超简单的游戏有 x 颗石子的 SG 值显然就是 x。

其实，n 堆石子的 Nim 游戏本身不就是 n 个 “任取石子游戏” 的和吗？

所以，对于我们来说，SG 函数与 “游戏的和” 的概念不是让我们去组合、制造稀奇古怪的游戏，而是把遇到的看上去有些复杂的游戏试图分成若干个子游戏，对于每个比原游戏简化很多的子游戏找出它的 SG 函数，然后全部异或起来就得到了原游戏的 SG 函数，就可以解决原游戏了。

---

好啦，从这里开始都是我自己写的啦！

对于 SG 函数，我也总结一下自己的想法吧。

• 必败点的 SG 函数值为 0
• 必胜点的 SG 函数值大于 0
• 一个必败点的后继节点必然全是必胜点
• 一个必胜点的后继节点中必然有必败点
• 一个SG值为 $k,k>0$的点，必然能转到 SG 值为 $x,x\in [0,k-1]$的点

想清楚了上面这 5 点，看懂上面那两篇文章也就不难啦～

Nim 游戏模板：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,a,ans;
    cin>>n>>ans;
    for(int i=2;i<=n;i++)cin>>a,ans^=a;
    if(ans)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

SG 函数模板（有向无环图博弈 SG 函数）：

/*
题意：给出一个有向无环图，再给出 n 个棋子所在的点的编号
每次双方可以任选某一颗可移动的棋子移动到它所在的点的某一个后继节点
可移动指的是它所在的点有后继节点
若某方无法移动则该方判输
求先手是否必胜
点数<=1000，有多组游戏
*/

#include <bits/stdc++.h>

#define NS (1005)

using namespace std;

template <typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int n, m, deg[NS], sg[NS];

vector<int> g[NS], gi[NS];

queue<int> que;

bool book[NS];

void cal(int a)//计算点 a 的 SG 值
{
    for (int i = 0; i < gi[a].size(); i += 1) book[sg[gi[a][i]]] = 1;
    sg[a] = 0; while (book[sg[a]]) sg[a]++;
    for (int i = 0; i < gi[a].size(); i += 1) book[sg[gi[a][i]]] = 0;
}

int main(int argc, char const* argv[])
{
    IN(n);
    for (int i = 0; i < n; i += 1)
    {
        IN(deg[i]);
        for (int j = 1, a; j <= deg[i]; j += 1)
            IN(a), g[a].push_back(i), gi[i].push_back(a);
        if (!deg[i]) que.push(i);
    }
    while (!que.empty())//按拓扑序来算 SG 值
    {
        int F = que.front(); que.pop();
        for (int i = 0, tmp; i < g[F].size(); i += 1)
            if (tmp = g[F][i], --deg[tmp] == 0)
                cal(tmp), que.push(tmp);
    }
    while (IN(m), m)
    {
        int res = 0;
        for (int i = 1, j; i <= m; i += 1) IN(j), res ^= sg[j];
        if (res) puts("WIN"); else puts("LOSE");
    }
    return 0;
}

Finish

至此，博弈论入门知识已经讲得差不多啦 QvQ

但貌似还有更多更难的问题等着我们去解决呀！QvQ