2025.6.27 花了一上午增添了新内容，翻新了威佐夫博弈证明。大幅更新了自己理解下的 SG 函数，添加了自己 yy 的 trick。

0. 前言

对于在信息学竞赛中的博弈论，我们研究的是组合博弈问题。在实际考察中会结合其他知识点考察，例如动态规划或者贪心等，建立模型来解决问题。

本文建议读者看到模型后可以停下来思考思考，让后再看证明。

说半家桶是因为内容还不全，不能作为 OI 中的全家桶，但是足以应付一部分问题了。

而对于例题讲解来说，我更喜欢的方式就是在许多不同的题目中总结模型出来，并且会结合之前的知识点来进行讲解，所以建议是都研读 www。

~~有谁注意到标题其实有一个回文串了。~~

1. 组合博弈与博弈基础

对于组合博弈，我们用两种类型：公平组合游戏和非公平组合游戏来区别，定义如下：

1.1 公平组合与非公平组合

公平组合游戏：

由两名玩家交替行动；
任意一个游戏者在某一确定状态可以作出的决策集合只与当前的状态有关，而与游戏者无关；
游戏中的同一个状态不可能多次抵达，游戏以玩家无法行动为结束，且游戏一定会在有限步后以非平局结束。

例如取数游戏，Nim 游戏等，是公平组合游戏，我们下文会提到。

而非公平组合游戏，即在某一确定状态下作出的决策集合与游戏者有关。例如国际象棋，五子棋等是非公平组合游戏，因为双方不能使用对方的棋子。

以上是 Oi-Wiki 的内容，可能很抽象，但是提取重点的来说：

公平组合游戏：可允许的操作和当前局面状态有关，而不和玩家有关（这样就很公平，因为和玩家无关啦）。
非公平组合游戏：可允许的操作与当前操作的玩家有关（因为和玩家有关，我不能动你的棋子，这显然很不公平 www）。

1.2 先手，后手，必胜必输局面

~~本手，妙手，俗手。~~

接下来我们定义几个名词：

局面：我们把游戏过程中面临的状态我们称作为 “局面”。
先手：整局游戏第一个行动的。
后手：整局游戏第二个行动的。

这几个名词还是比较简单的。

必败局面：即无论采取任何行动都无法胜利，都会输掉游戏。
必胜局面：即在某一局面下存在某种行动，使得后手行动陷入必败局面。

注意其中名词加粗的部分。

1.3 先手必胜与先手必败

先手必胜状态： 先手行动以后，可以让剩余的状态变成必败状态 留给对手。(即可以走到某一个必败状态)
先手必败状态： 不管怎么操作，都达不到必败状态，换句话说，如果无论怎么行动都只能达到一个先手必胜状态留给对手，那么对手（后手）必胜，先手必败。（即走不到任何一个必败状态）

有如下定理：

没有后继状态的状态是必败状态。
一个状态是必胜状态当且仅当存在至少一个必败状态为它的后继状态。
一个状态是必败状态当且仅当它的所有后继状态均为必胜状态。

1.4 必胜点与必败点

必败点，又称 $P$ 点，表示前一个选手将取胜的点称作必败点。
必胜点，又称 $N$ 点，表示下一个选手将取胜的点称作必胜点。

所有终结点都是必败点。
从任何必胜点操作，至少存在一种方案可以进入必败点。
无论如何操作，必败点只能进入必胜点（不然先手怎么赢）。

2. 基本公平组合游戏

接下来我们看见一堆取东西的游戏 www。

2.1 Nim 游戏

给定 $n$ 堆物品，第 $i$ 堆物品有 $a_{i}$ 个。两名玩家分别行动，每次可以任选一堆，取出任意多个物品，可以一把取光但是不能不取。取走最后一个物品的人胜利。

~~Vim 游戏？~~

Nim 游戏没有平局，只有先手必胜和先手必败两种情况。我们有如下的判定定理来判定：

Nim 博弈先手必胜，当且仅当 $a_{1} \operatorname{xor} a_{2} \operatorname{xor} \dots \operatorname{xor} a_{n} \neq 0$ 。

其中 $\operatorname{xor}$ 代表异或操作。

证明如下：

我们考虑，所有物品都被取光当然是一个必败局面（对手取走最后一件物品，已经取得胜利），此时 $a_{1} \operatorname{xor} a_{2} \operatorname{xor} \dots \operatorname{xor} a_{n} = 0$ 。

对于一个局面如果 $a_{1} \operatorname{xor} a_{2} \operatorname{xor} \dots \operatorname{xor} a_{n} \neq 0$ ，那么设 $x$ 二进制表示下最高位的 $1$ 在第 $k$ 位，那么至少存在一堆物品使得它的第 $k$ 位为 $1$ 。显然 $a_{i} \operatorname{xor} x < a_{i}$ ，我们就从 $a_{i}$ 堆中取走若干物品，使其变为 $a_{i} \operatorname{xor} x$ ，这个操作我们就是尝试将局面变为 $a_{1} \operatorname{xor} a_{2} \operatorname{xor} \dots \operatorname{xor} a_{n} = 0$ ，容易证明这是最优策略。

对于任意一个局面，若 $a_{1} \operatorname{xor} a_{2} \operatorname{xor} \dots \operatorname{xor} a_{n} = 0$ ，容易证明无论如何取物品，最后的局面异或起来都无法不等于 $0$ ，那么综上所述 $a_{1} \operatorname{xor} a_{2} \operatorname{xor} \dots \operatorname{xor} a_{n} \neq 0$ ，一定是必胜局面，一定存在一个情况让对手面临各堆物品异或起来为 $0$ 的局面，证毕。

P2197 NIM游戏

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=1e5+15;
int T,n;

int main(){
    cin>>T;
    while(T--){
        cin>>n;
        int ans=0;
        for(int i=1;i<=n;i++){
            int x;
            cin>>x;
            ans^=x;
        }
        if(ans) cout<<"Yes\n";
        else cout<<"No\n";
    }
    return 0;
}

2.2 Nim升级版——NimK

$n$ 堆石子，每次从不超过 $k$ 堆中取任意多个石子，取走最后一个物品的人胜利。

结论如下：

把 $n$ 堆石子用二进制数表示，统计二进制数上 $1$ 的个数，若每一位上 $1$ 的个数 $num_{1} \bmod (k+1)$ 全部为 $0$ ，则先手必胜，否则先手必败。

证明还是类似于 Nim 游戏：

所有物品都被取光当然是一个必败局面，即全为 $0$ 。
任意一个先手必败状态，一次操作后必然会到达必胜状态（因为游戏是交替进行的。）在某一次移动中，至少有一堆被改变，也就是说至少有一个二进制位被改变。因为最多动 $k$ 堆，所以对于任意一个二进制位， $1$ 的个数最多改变 $k$ 。而由于原先的总数为 $k+1$ 的整数倍，那么改变后必然不可能是 $k+1$ 的整数倍。所以在必败状态下必然能转移到必胜状态。
而对于先手必胜，总有一种操作使其走到必败状态，即证明有一种方法让第 $i$ $i$ 位回到 $k+1$ $k + 1$ 的整数倍。有一个比较显然的性质，对于那些已经改变的 $m$ $m$ 堆，当前位可以自由选择 1 或 0。我们设除去已经更改的 $m$ $m$ 堆，剩下堆 $i$ $i$ 位上 $1$ $1$ 的总和为 $sum$ $s u m$ 。考虑分类讨论：
- $sum\le k-m$ ，此时我们可以将堆上的 $1$ 全部拿掉，让后让拿 $m$ 堆得 $i$ 位全部为 0。
- $sum>k-m$ ，此时我们在之前改变的 $m$ 堆中选择 $k+1-sum$ 堆，将他们的第 $i$ 位设置成 1。剩下的设置成 0。由于 $k+1-sum<k+1-(k-m)<m+1$ ,也就是说 $k+1-sum\le m$ ，故这是可以达到的。

故存在，证毕。

例题：SDOI2011黑白棋

2.3 阶梯 Nim 游戏

$n$ 堆石子，编号 1 到 $n$ 。初始第 $n$ 堆石子数为 $a_{i}$ ，保证单调不降。轮流取石子，每次从任意一堆拿走任意个，要求取完后每一堆剩余石子个数单调不降（没有石子的记为 0 个），先不能行动者败。

或者换一种表述：

有 $n$ 堆石子。除了第一堆外，每堆石子个数都不少于前一堆的石子个数。两人轮流操作。每次操作可以从一堆石子中移走任意多颗石子，但是要保证操作后仍然满足初始时的条件。没有石子可移动的人就输掉了游戏。

因为堆数是单调递增的，像一个阶梯，我们在阶梯取石子。所以叫阶梯 Nim 游戏。

结论：

阶梯 nim 的游戏结果与只看奇数堆的石子数的普通 nim 结果一致。

考虑证明：

首先末态一定是 $a_{1} \operatorname{xor} a_{3} \operatorname{xor} a_{5}\dots=0$ ，那么如果初态 $a_{1} \operatorname{xor} a_{3} \operatorname{xor} a_{5}\dots=0$ ，就一定存在一种方式将某奇数台阶的石子移动到偶数台阶上使得异或和为 0 。这样，不管后手的人是把奇数台阶的移动到偶数台阶还是相反，先手都一定存在一种方案使得异或和为 0 ,这样就一定能转移到末态，先手就赢了！

板题：

P3480

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=1520;
int T,n,a[MN],b[MN];

void solve(){
    cin>>n;
    int x=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i]=a[i]-a[i-1];
    }
    for(int i=n;i>=1;i-=2) x^=b[i];
    if(x) cout<<"TAK\n";
    else cout<<"NIE\n";
}

int main(){
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

2.4 巴什博弈 Bash Game

~~Bash 命令行？~~

只有一堆石子，个数为 $n$ 个，两名玩家轮流在石子堆中拿石子，每次至少取 1 个，至多取 $m$ 个，最后一个取走石子的玩家为胜者。

结论如下：

若 $(m+1)|n$ ，则先手必败，否则先手必胜。

证明如下：

当 $n\le m$ 时，显然先手必胜。
当 $n=m+1$ 时，先手最多取走 $m$ 个，无论取走多少个后手必胜。
若 $(m+1)|n$ ，假设先手拿走 $x$ 个，那么后手一定可以拿走 $(m+1)-x$ 个，这样无论怎么拿剩下的石头个数都是 $(m+1)$ 的倍数，那么最后一次取的石头一定还剩下 $m+1$ 个，显然必败。否则，先手取走模 $(m+1)$ 的手头，此时转化为 $(m+1)|n$ ，那么后手必败。

得证。

有板题：HDU4764

2.5 威佐夫博弈

有两堆石子，石子数可以不同。两人轮流取石子，每次可以在一堆中取，或者从两堆中取走相同个数的石子，数量不限，取走最后一个石头的人获胜。判定先手是否必胜。

同步发表于：P2252题解

威佐夫博弈不同于Nim游戏与巴什博奕，它的特殊之处在于不能将两堆石子分开分析。

证明可以不看的 www。

因为只有两堆石子，先进行一步转化给他丢到二维坐标系上，那么坐标 $(x,y)$ 就表示两堆的石子数量。

我们考虑观察性质，我们可以枚举几个必败状态，例如 (0,0),(1,2),(3,5),(4,7)……

我们观察状态，可以发现两个规律，我们假设从小到大排的第 $k$ 个必败状态是 $(x,y)$ ，并且 $x<y$ 。并且我们发现 $y=x+k$ 。这个说明的就是必败状态两个数的差值是递增的，所以也就说明了每一个必败状态的差值都各不相同。证明我们待会在来看。

那么原来的问题，我们可以把游戏转化为，棋盘上有一个点，每个人可以将棋子往下，向左或向左下移动若干的棋子，不能移动的人。能够一步移动到原点的点显然就是必胜点，假设我们给这些所有必胜点都染色的话，剩下的的没当中横纵坐标和最小的点就是下一个必败点，因为无论如何移动都会给对手留下一个必胜点。

我们借用梁唐的知乎博客的图，将必败点染色可以得到如下图：

从图中不难看出，必败点之间是无法一次移动就能得到的，换句话说可以一次移动到必败点的点都是必胜点，那么上图中除了必败点之外的点都是必胜点，并且每一个自然数必然只会被包含在一个必败状态之中。

那么根据图的一些奇妙性质，我们定义，先手必输的局势为奇异局势。不妨设 $(x,y)$ 为第 $k$ 个奇异局势。那么有如下性质：

$x$ 为前 $k$ 个奇异局势中最小没有出现过的正整数， $y=x+k$ 。
任何一个自然数都包含在有且仅有一个奇异局势中。
任何操作都会将奇异局势变成非奇异局势。（必胜必然走向必败）
可以采取适当的方法让非奇异局势变成奇异局势。（即必败走向必胜点）

第一个，考虑反证法，假设 $(a,a+k),(b,b+k)$ 是必败状态，并且 $a<b$ 。那么先手面临 $(b,b+k)$ 的时候，只需要在两堆当中同时取走 $b-a$ 个石子，那么给后手的局面就是 $(a,a+k)$ 。但是对于后手来说，这是一个必败的局面，那么 $(b,b+k)$ 不就是必胜状态了吗，矛盾，所以不存在两个必败局面的差值相等。

第二个个证明考虑反证法，我们需要证明两点：

任意自然数都出现过。
任意自然数只出现一次。

证明如下：

反证法，如果 $v$ 没有出现过，那么 $v$ 显然可以做一个新奇异局势的 $x$ 。
反证法，假设 $v$ 出现了两次，那么 $v$ 一定不是所在奇异局势的 $x$ ，那么 $v$ 只能同时是两个奇异局势的 $y$ ，但因为任意一个奇异局势的差值不相同，所以 $v$ 不可能存在。

第三个，我们考虑若取走一堆中的石子，那么两对石子的差值会改变，必将成为非奇异局势。若同时取走，因为同一个差值只会对应一种奇异局势，必将成为非奇异局势。

第四个是显然的，不证明。

那么现在问题在于我们如何快速找出一个通项公式使得对于第 $k$ 个必败局面，它的坐标是 $(x_{k},y_{k})$ 呢？

我们有 Betty 定理！

设 $a,b$ 是两个正无理数，且 $\dfrac{1}{a}+\dfrac{1}{b}=1$ 。
记 $P=\left\{ \lfloor a\times n \rfloor|n \in \mathbb{N}^{+} \right\},Q=\left\{ \lfloor b\times n \rfloor|n \in \mathbb{N}^{+} \right\}$ ，则 $P \cap Q=\varnothing,P \cup Q =\mathbb{N}^{+}$ 。

证明可以去网上看。

那不对啊，我们是自然数你这是无理数，你这八杆子打不着的东西拿出来用干啥啊。因为我们发现必败状态的通项和Betty定理序列很像。

我们不妨假设存在这样的 $a,b$ 同时满足 Betty 定理和必败状态的性质，当然无理数不可能作为坐标出现啦，我们当然要让它变为整数。

那怎么办，Betty 有一个推论就是：

任何正整数都可刚好以一种形式表示为不大于其中一个无理数的正整数倍的最大整数。

从定理直接推，那么有如下式子：

\begin{cases} \lfloor a\times n\rfloor +n = \lfloor b\times n \rfloor \\ \frac{1}{a}+\frac{1}{b}=1 \end{cases}

解第一个方程：

\begin{aligned} \lfloor b\times n \rfloor & = \lfloor a\times n\rfloor +n \\ & = \lfloor a\times n +n \rfloor \\ & = \lfloor (a+1) \times n\rfloor \\ \therefore b &= a+1 \end{aligned}

那么代入第二个方程有：

\frac{1}{a}+\frac{1}{a+1}=1

开解！

\begin{aligned} & \frac{1}{a} + \frac{1}{a+1} = 1 \\ & \frac{1}{a} =\frac{a+1}{a(a+1)} \\ & \frac{1}{a+1} = \frac{a}{a(a+1)} \\ & \therefore \frac{a+1}{a(a+1)}+\frac{a}{a(a+1)}=1 \\ & \to \frac{2a+1}{a(a+1)}=1 \\ & \therefore 2a+1=a(a+1)=a^2 +a \\ & \therefore 2a+1-a^2 -a =0 \\ & \therefore a^2-a-1=0 \end{aligned}

利用初中知识不难得出 $a=\dfrac{1+\sqrt{5}}{2}$ 或 $\dfrac{1-\sqrt{5}}{2}$ 。

完了吗？敢说完了的扣 114514 分 (≧m≦)

设 $a,b$ 是两个正无理数，且 $\dfrac{1}{a}+\dfrac{1}{b}=1$ 。

正无理数！所以解为 $a=\dfrac{1+\sqrt{5}}{2}$ 。

综上，假设两堆石子为 $(x,y),x<y$ 。

那么先手必败，当且仅当：

(y-x) \times \frac{\sqrt{5}+1}{2}=x

其中， $\dfrac{\sqrt{5}+1}{2}$ 就是黄金分割数，很神奇的。

题目：P2252

#include<bits/stdc++.h>
#define double long long
using namespace std;
const double hjfg=((1.0+sqrt(5.0))/2.0);
double a,b;

int main(){
    cin>>a>>b;
    if(a>b) swap(a,b);
    double ans=(b-a)*((1.0+sqrtl(5.0))/2.0);
    if(ans==a) cout<<0;
    else cout<<1;
    return 0;
}

2.6 斐波那契博弈

有一堆个数为 $n,(n\ge 2)$ 的石子，游戏双方轮流取石子，规则如下：

先手不能第一次全取完，至少取 $1$ 颗。
之后每次取的石子个数至少为 $1$ ，至多为对手所取的石子数的 $2$ 倍。

还是最后一个取走石子的为赢家。

先手必败，当且仅当石子数为斐波那契数

先证明必要性，斐波那契数一定先手必败，可以用数学归纳法，大致思路就是一定能拆成两堆斐波那契数，不论先手怎样取，后手总能取到最后一颗

然后证明充分性，由齐肯多夫定理定理：

任何正整数可以表示为若干个不连续的斐波那契数之和

那么这样就回到了斐波那契数列里，可以证明。

考虑最优决策：

若正整数 $n$ 不为斐波那契数，那么用上述定理表示后，最小的那一堆个数即为答案。

证明因为不存在相邻的斐波那契数，那么显然有 $f_{j}>2 \times f_{i}$ ，只要我取第一个，那么对手一定取不完下一个，让后我捡漏，以此类推，一定能取道最后一个石子。

板题：P6847

#include<bits/stdc++.h>
#define int long long
using namespace std;

signed main(){
    int n;
    cin>>n;
    while(n){
        if(n==1){
            cout<<1;
            break;
        }
        if(n==2){
            cout<<2;
            break;
        }
        int a=1,b=2,c=3;
        while(c<n) a=b,b=c,c=a+b;
        if(c==n){
            cout<<n;
            break;
        }
        n-=b;
    }
    return 0;
}

2.7 总结

有一张来自HansLimon的好图：

以上都是一些基本公平组合游戏，我们通过分析必胜状态与必败状态的位置来计算。接下来我们会介绍公平组合游戏的万能工具，SG 函数。

3. SG与有向图游戏

3.1 有向图游戏

给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判负。该游戏被称为有向图游戏。

任何一个公平组合游戏都可以转化为有向图游戏。具体方法是，把每个局面看成图中的一个节点，并且从每个局面向沿着合法行动能够到达的下一个局面连有向边。转化为有向图游戏，也称绘制了它的博弈状态图（简称博弈图或游戏图）。

而对于有向图游戏中的每一个节点，都代表当前子游戏的状态。

3.2 Mex 运算

设 $S$ 表示一个非负整数集合。定义 $\operatorname{mex}(S)$ 为求出不属于集合S的最小非负整数的运算，即：

\operatorname{mex}(S)=\min \left\{ x \right\},x\in \mathbb{N}^{+},x\notin S

$\operatorname{mex}(S)$ 的求法我们在做题中一般推式子用。如果真要单纯考，还真考过，可以考虑用 set 来实现，把 $S$ 中的数都放入 set 中，维护两个操作：

加入 $x$ 操作：在 set 删除 $x$ ，前提是 $x$ 这个数出现第一次。
删除 $x$ 操作：在 set 加入 $x$ ，前提是 $x$ 是剩下的唯一一个 $x$ 。
查询操作：查询 $set$ 里的第一个数。

例题：abc330e

3.3 SG 函数

在有向图游戏中，对于每个节点 $x$ ，设从 $x$ 除法共有 $k$ 条有向边，分别到达节点 $y_{1},y_{2},\dots ,y_{k}$ ，定义 $\operatorname{SG}(x)$ 表示为 $x$ 的后继节点 $y_{1},y_{2},\dots ,y_{k}$ 的 $\operatorname{SG}$ 函数值所构成的集合再执行 $\operatorname{mex}$ 运算的结果，即：

\operatorname{SG}(x)=\operatorname{mex}(\left\{ \operatorname{SG}(y_{1}),\operatorname{SG}(y_{2}),\dots,\operatorname{SG}(y_{k}) \right\})

特别的，整个有向图游戏 $G$ 的 $\operatorname{SG}$ 函数值定义为有向图起点 $s$ 的 $\operatorname{SG}$ 函数值，即 $\operatorname{SG}(G)=\operatorname{SG}(s)$ 。

没错，你是不是发现了，SG 函数其实是递归求解的，，计算一个位置的 SG 值需要知道其所有后继位置的 SG 值。

3.4 必胜与必败判定,SG 定理

判定法则（同时也是定义）如下：

有向图某个局面必胜，当且仅当该局面对应节点的 $\operatorname{SG}$ 函数值大于 $0$ 。
有向图某个局面必胜，当且仅当该局面对应节点的 $\operatorname{SG}$ 函数值等于 $0$ 。

凭什么我们这么规定！

那我们把前面我们所说的必胜点和必败点联系起来，对于 SG 函数的定义有：

终止状态（无合法移动）： $\operatorname{SG}=0$ （必败点，P-position）。
非终止状态： $\operatorname{SG}(x)=\operatorname{mex}(\left\{ \operatorname{SG}(y_{1}),\operatorname{SG}(y_{2}),\dots,\operatorname{SG}(y_{k}) \right\})$ 。

那么显然有：

$\operatorname{SG}=0$ ：所有后续都是必胜点（都可以不走到终止状态），当前玩家无法避免失败。因此是必败点。
$\operatorname{SG} \neq 0$ ：至少有一个移动可使对手进入必败点，因为根据 $\operatorname{mex}$ 运算的性质 $\operatorname{SG}=0$ 出现了。因此是必胜点。

同时思考我们上面所说的 SG 函数的递归性质的计算，你有没有发现什么？

而根据上面我们所说的，有向图游戏是一个 DAG，并且节点状态唯一确定不重叠的。我们有没有想到什么，没错，动态规划的转移也是这样的！

动态规划当前问题由子问题确定当前解，而 SG 函数由子游戏的 SG 确定当前的解；SG 计算利用 DAG 的拓扑序计算（从终止反向递推），而动态规划状态转移也是 DAG 上的转移。当前节点的 SG
函数只依赖后续状态，而不依赖历史，也就是无后效性，这个 DP 同样也满足！

那么我们怎么利用 DP 的思想定义 SG 函数呢？

状态：就是有向图游戏上的一个局面。
转移：有向图游戏上的合法移动。
答案：即当前局面在最优策略下的的博弈论特征值（即 SG 函数或其他）

其实，SG函数的递归计算本质上就是在动态地判断每个状态是必胜还是必败，类似于在 DAG 上的动态规划过程，我们利用 $\operatorname{mex}$ 运算来保证 SG 函数的求解正确性。我们通过终止向前递推我们游戏的过程。

那么，根据上面我们所说的，SG 函数可以通过记忆化搜索避免重复计算（类似 DP 的记忆化搜索写法），或者通过常规的动态规划我们可以求解。那么，也就是说，通过动态规划的方法我们也是可以求解出博弈论的解，这个可是一大考点，我们把两大很难的内容融合到一起就会出现很多的考点，在接下来的博弈论应用这我们会详细的提到。

接下来我们来看有向图游戏的和，即 SG 定理，我们这么定义：

设 $G_{1},G_{2},\dots,G_{m}$ 是 $m$ 个子有向图游戏。定义有向图游戏 $G$ ，它的行动规则是任选某个有向图游戏 $G_{i}$ ，并在 $G_{i}$ 上行动一步。 $G$ 被称为有向图游戏 $G_{1},G_{2},\dots,G_{m}$ 的和。

有向图游戏的和的 $\operatorname{SG}$ 函数值等于它包含的各个子游戏 $\operatorname{SG}$ 函数值的异或和，即：

\operatorname{SG}(G)= \operatorname{SG} (G_{1}) \operatorname{xor} \operatorname{SG} (G_{2})\operatorname{xor} \dots \operatorname{SG} (G_{m})

这里给出一个性质，由 $\operatorname{mex}$ 得出某个状态的 SG 值一定在 $O(\sqrt{m})$ 以内，其中 $m$ 为有向图游戏的边数。

3.5 公平组合游戏为何结局注定？

下面的芝士了解即可。

你有没有好奇过，我们上面讲了那么多的基本公平组合游戏，为什么我们明明还没开始玩这个游戏，结局却已经命中注定了呢？

回顾我们之前所讲的公平组合游戏定义：

由两名玩家交替行动；
任意一个游戏者在某一确定状态可以作出的决策集合只与当前的状态有关，而与游戏者无关；
游戏中的同一个状态不可能多次抵达，游戏以玩家无法行动为结束，且游戏一定会在有限步后以非平局结束。

为何公平？在我们组合游戏理论中，“公平” 指的是：

规则对称：双方玩家在同一个游戏状态下可用的移动完全相同（不像象棋或围棋，双方棋子不同）。
无随机性：游戏过程有玩家决策决定，没有抽牌的随机因素。
终止性：游戏必然在有限步数内结束，不会无限循环。
完全信息：没有隐藏信息，双方对游戏状态完全知晓。

而我们上面一直所提到的最优策略，采取最优策略其实决定了你的结局走向。那么最优策略到底是什么？为什么先手有必胜必输这种状态？这里我们揭秘：

策梅洛定理：在有限步、无随机性、完全信息的两人博弈中，必然存在一个确定的最优策略，使得先手或后手一方有必胜策略，或双方至少能强制平局。

证明？

考虑数学归纳法，设 $n$ 是某一游戏的最大步长，比如我们下棋，玩很多很多次，其中最多回合的一次，是大战300回合后我赢了，那么 $n=600$ 因为我们下了 600 次棋。对 $n$ 进行数学归纳法：

当 $n=1$ ，显然，只用走一步，就可决定输赢。按照游戏的规定，也许有胜负和三种，那么玩家 1 显然选择胜的走法，于是满足玩家 1 有必胜策略。
假设当 $i\le n$ 时命题成立，考虑 $n+1$ 时的子游戏，除去玩家 1 走的第一步以后的游戏部分。玩家1第一步的每一种走法都会产生一个新游戏起始状态，它的最大步长是 $\le n$ 的，而根据我们的假设，每个子游戏有唯一确定的结果，玩家 1 必然会赢、输或者和。于是等价于 $n=1$ 的情况了！相当于玩家 1 在第一步的时候来选择进入哪个游戏，是自己必赢还是必输还是必和。

综上，该结论对于所有正整数成立，证毕。

由于公平组合游戏通常没有平局（游戏以某一方无法移动结束），所以每个状态要么是必胜点，要么是必败点，我们的最优策略就是确保自己始终处于必胜点。，而我们通过 SG 函数和必胜必败点分析就能得出计算胜负的数学方法。

必胜策略：如果当前玩家处于 必胜点（N-position），则存在至少一个移动，使得对手进入 必败点（P-position）。那么我们始终选择让对手进入必败点的移动，即可确保胜利。
必败策略：- 如果当前玩家处于 必败点（P-position），则无论怎么移动，对手都能采取最优策略获胜。此时，最优策略是尽量拖延游戏，或希望对手犯错。

那么，根据定理，只要玩家遵循最优策略，结局就已被初始状态决定。奇怪的宿命论出现了！而最优策略就是利用 SG 函数或必胜/必败点分析，确保对手始终处于劣势。然而，理论上我们固定了，但是实际对局中玩家可能犯错，这个时候就要重新计算了，正如我们上面所提到的必胜点：存在至少一个。所以必胜点也可以走向必败点的。

综上，我们分析了为什么公平组合游戏结局注定，必胜必输状态是怎么出现的以及公平组合游戏的性质。

3.6 NIM 游戏与 SG 函数的结合

对于单堆的 Nim 游戏，我们很容易计算它的 $\operatorname{SG}$ 值，设 $\operatorname{SG}(m)$ 表示剩余 $m$ 个式子状态的函数值，显然 $\operatorname{SG}(0)=0$ ，那么以此类推， $\operatorname{SG}(1)=1,\operatorname{SG}(2)=2,\dots,\operatorname{SG}(n)=n$ 。因此，当石子数不为 $0$ 时为必胜态。

而对于更多的，它们所有的堆都可以划分为一个单独的有向图游戏，而每一个有向图游戏的 $\operatorname{SG}$ 函数值就是上面所以到的。那么，我们可以根据 $\operatorname{SG}$ 定理，将它们给和起来，那么答案就是：

\begin{aligned} \operatorname{SG}(G) & =\operatorname{SG}(G_{1}) \operatorname{xor} \operatorname{SG}(G_{2)} \operatorname{xor} \dots \operatorname{xor} \operatorname{SG}(G_{n}) \\ & = a_{1} \operatorname{xor} a_{2} \operatorname{xor} \dots \operatorname{xor} a_{n} \end{aligned}

那么，我们就得到的 Nim 游戏的经典结论，是不是很神奇。

对于博弈的大部分问题，只要SG值相同，就可以互相转化，而对于 SG 函数来说，其求解依靠将一个总游戏划分成几个子游戏，简化问题逐个击破，通过定理就可以把他们的结果结合起来。

3.7 SG例题与复杂博弈论技巧

在实际应用方面，我们介绍的是子游戏的划分以及 SG 函数状态刻画，以及求解。照应我们上面所说的内容,**对于博弈的大部分问题，只要SG值相同，就可以互相转化，而对于 SG 函数来说，其求解依靠将一个总游戏划分成几个子游戏，简化问题逐个击破，通过定理就可以把他们的结果结合起来。

P1290

显然是公平组合游戏。

对于这种没有明显结论的博弈论题，我们先处理出特殊情况。

而对于本题来说，显然我们划分的子游戏就是每个人手里握的求。

我们考虑最终情况：一个数是 $x$ ，而另一个是 0，那么先手必败（因为游戏已经结束了）。

剩下的情况就是握着两个数，不妨设为 $x,y$ ，其中 $x>y$ 。

那么根据题意有：

\operatorname{SG}(n,m)=\operatorname{mex}(\left\{ \operatorname{SG}(n-m,m),\operatorname{SG}(n-2m,m),\dots,\operatorname{SG}(m,n \bmod m) \right\})

考虑里面怎么求，注意到：

\operatorname{SG}(n-m,m)=\operatorname{mex}(\left\{ \operatorname{SG}(n-2m,m),\operatorname{SG}(n-3m,m),\dots,\operatorname{SG}(m,n \bmod m) \right\})

同理可以迭代下去，所以除了 $\operatorname{SG}(m,n \bmod m)$ 以外其他都可以由他迭代出来，考虑如何求出来：

假设 $\operatorname{SG}(m,n \bmod m)=0$ ，设 $k=\dfrac{n}{m}$ ，那么有 $\operatorname{SG}(n-(k-1)\times m,m)=\operatorname{mex}\left\{ \operatorname{SG}(m,n \bmod m) \right\}$ 成立。

假设 $\operatorname{SG}(m,n \bmod m)=1$ ，那么 $\operatorname{SG}(n-(k-1)\times m,m)=\operatorname{mex}\left\{ \operatorname{SG}(m,n \bmod m) \right\}$ 不成立。

由此可以看出，若 $k=1,\operatorname{SG}(n,m)=[\operatorname{SG}(m,n \bmod m)=0]$ ，否则是 1。

一般来说，我们对于 SG 函数的求解，最常规的套路就是：暴力，找规律。或者打表。 大部分题都可以这么进行操作，有的时候需要进一步转化模型，当然那就是后面再说了。

这是标准的辗转相除的递推式子，用 $\gcd$ 的写法即可实现：

#include<bits/stdc++.h>
using namespace std;
int T;

int dfs(int x,int y,int p){
    if(x==y) return p;
    if(y/x>=2) return p;
    return dfs(y-x,x,p^1);
}

void solve(){
    int m,n;
    cin>>m>>n;
    if(m>n) swap(m,n);
    if(dfs(m,n,0)==0) cout<<"Stan wins\n";
    else cout<<"Ollie wins\n";
}

int main(){
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

P3179

对不起对不起忘放这个题了 (๑• . •๑)。

而本题，我们和上面，首先我们要分解出子游戏，这样我们才能利用 SG 函数求解。若我们无法分解为子游戏，我们需要考虑其他方法求解。

结论就是，每一个白色格子都是独立的，即一个白色格子处的决策与其他格子的状态无关，这样我们就划分出来子游戏了。

等等等等，你咋证明这个满足我们上面所说的有向图游戏的性质啊！

我们考虑，因为一个白格子可能会影响其他白格的情况，当且仅当这个白格翻转后有产生与其他白格重合的白格。这个时候我们应当把重合格子视为黑色格子，但是如果我们认为他们是两个独立的白格子，这显然是等价的，根据 SG 游戏和是异或的，异或和为 0，所以对这两个白色格子操作没有任何意义，得证。

感性理解就是一方操作了这两个白格中的一个，另一方可以立刻操作另一个，局势不发生变化。

我们对于翻棋子游戏，解法就是把初始状态的 SG 值即所有棋子的 SG 值异或和求出来，为 0 则必败否则必胜。

简单暴力，我们从后往前进行卡搜绿，求出每一个白色格子出现在每一个位置的 SG 值，对于每一个白色格子，考虑枚举 $k$ 的值，这个时候新状态的 SG 值是 $\operatorname{SG}(x+ix)$ ，的异或和，其中 $(1 \le i \le k-1)$ 。最后再求出所有转移到的状态 SG 值加上一个 0 的 mex。复杂度是 $\sum\limits_{i=1}^n \lfloor \frac{n}{i} \rfloor =O(n \log n)$ 。

不难注意到是整除分块，考虑只维护 $\lfloor \dfrac{n}{x} \rfloor$ 个不同的根号个 $x$ 的 SG 函数，仍然按 $x$ 从大到小考虑。对于每一个 $x$ 考虑它的所有转移到的状态 SG 值仍然有如上性质，可以考虑 $\lfloor \dfrac{n}{x} \rfloor$ 相同的一起计算，这是整除分块，时间复杂度是 $O(n ^{\frac{3}{4}})$ ，可以通过。

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=3e6+15;
int sg[2][MN],rt[MN],pos[MN],tot,n,n2,T;

inline int SG(int x)
{
	return ((x=n/(n/x))>n2)?sg[1][n/x]:sg[0][x];
}

void init(){
    for(int l=1,r;l<=n;l=r+1){
        r=n/(n/l);
        rt[++tot]=r;
    }
    ++tot;
    while(--tot){
        int x=rt[tot],y=0,z=1;
        pos[y]=tot;
        for(int i=x*2,j;i<=n;i=j+x){
            j=n/(n/i)/x*x,pos[y^SG(j)]=tot;
            ((j-i)/x&1^1)&&(y^=SG(j));
        }
        while(pos[z]==tot) ++z;
        (x>n2)?sg[1][n/x]=z:sg[0][x]=z;
    }
}

int main(){
    cin>>n>>T;
    while(n2*n2<=n) ++n2;
    n2--;
    init();
    while(T--){
        int w,x=0;
        cin>>w;
        for(int i=1;i<=w;i++){
            int awa;
            cin>>awa;
            x^=SG(awa);
        }
        cout<<(x?"Yes":"No")<<'\n';
    }

    return 0;
}

agc017d

还是我们的思路，分解子游戏。

首先源命题删边的操作，我们转化为删一个子树的操作（不能删整棵树），显然这个游戏是公平组合游戏，问我们初始状态，考虑利用 SG 函数求解。

首先，刻画游戏，我们终止状态是什么，显然当这个一个几点没有孩子节点的时候就是终止节点，那么 SG 函数为 0。

让后考虑我们怎么进行转移，还是上面我们所提到过的，对于这种没有明显结论的博弈论题，我们先处理出特殊情况。

$x$ 没有儿子，显然 SG 为 0。
$x$ $x$ 有一个儿子，设为 $y$ $y$ ，我们考虑证明 $\operatorname{SG}(x)=\operatorname{SG}(y)+1$ $S G (x) = S G (y) + 1$ 。
- 删除以 $y$ 为根的子树，显然 SG 为 0。
- 删除其他子树，显然这个子树在以 $y$ 为根的子树内，根据数学归纳法，SG 中 $0,1,\dots,\operatorname{SG}(y)-1$ 都出现了，则 $\operatorname{SG}(x)=\operatorname{mex}\left\{ 1,2,\dots,\operatorname{SG}(y) \right\}=\operatorname{SG}(y)+1$ 。
若 $x$ 有多个儿子，此时可以继续划分为好几个子游戏，根据 SG 定理结合起来即使答案。
所以，SG 函数求解如下：

\operatorname{SG}(x)= \begin{cases} 0 & \text{x has no son} \\ \\ \operatorname{xor}_{y\in son(x)} \operatorname{SG}(y)+1 & \text{otherwise} \end{cases}

时间复杂度 $O(n)$ 。

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=1e5+15;
int f[MN],n;
vector<int> adj[MN];

void dfs(int u,int pre){
    f[u]=0;
    for(auto v:adj[u]){
        if(v==pre) continue;
        dfs(v,u);
        f[u]^=f[v]+1;
    }
}

signed main(){
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1,0);
    cout<<(f[1]?"Alice":"Bob");
    return 0;
}

P7864

还是上面我们所提到过的，但是我们在增广一下，对于这种没有明显结论的博弈论题，我们先处理出特殊情况。在从特殊情况推广到一般情况。这也是大部分 OI 题的常规思路。

首先，树是一条链怎么做，经过手模显然在两端取，那么为偶数的时候先手必胜，反之为奇数的时候先手必败。

其次，我们考虑存在一个父节点，该节点存在多个叶子节点的形式，最经典的就是菊花图，那么有：

若只有一个叶子，显然先手必败。
若有多个叶子，那么先手可以把叶子节点拿到只剩下一个，那么就把必败的局面传给对方，因此先手必胜。

考虑推广但一般情况，就是将根几点当成树的一部分结构，那么结构因为是公平组合游戏，那么一定是 P 点或者 N 点，若是 P 状态，我们直接把叶子节点全部拿完，如果是 N 状态，我们就只剩下一个叶子节点。但是对于局面来说，先手都是具有操控全的。

最后，我们推广到一般性情况。对于所有的第二种情况，先手都可以操纵，也就是说情况 2 是必胜态。如果否则一定存在若干个链条使得所有叶子节点都没有兄弟。这样的话我们需要判断的链条的长度，也就是从该叶子节点出发到达的第一个不是只有一个子节点的父节点，也就是直到一种情况 2 出现。因此我们计算出所有链条的长度，如果存在奇数，先手必胜；如果全是偶数，则后手必胜。

时间复杂度 $O(n)$ 。

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=1e6+15;
int T,n,fa[MN],dg[MN];

void clear(){
    for(int i=1;i<=n;i++) dg[i]=fa[i]=0;
}

void solve(){
    cin>>n;
    clear();
    for(int i=2;i<=n;i++){
        cin>>fa[i];
        dg[fa[i]]++;
    }
    for(int i=1;i<=n;i++){
        if(dg[i]) continue;
        int pre=fa[i],len=0;
        while(dg[pre]==1){
            pre=fa[pre];
            len++;
        }
        len++;
        if(len&1){
            cout<<1<<'\n';
            return;
        }
    }
    cout<<"0\n";
}

int main(){
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

4. 反常游戏与反SG游戏

4.1 Anti-Nim游戏

是这样的：

有 $n$ 堆石子，两个人可以从任意一堆石子中拿任意多个石子(不能不拿)，拿走最后一个石子的人失败`。

不难发现和 Nim 游戏不同的一点就是胜利条件变了，不过条件还是可以推的。

先手必胜有两种情况：

对于所有石子都只有一个，且游戏的 $\operatorname{SG}$ 值为 0。
至少一堆石子多于一个，且游戏的 $\operatorname{SG}$ 不为 0。

游戏分为三种情况：

当每堆只有一个石子
异或值为 0 时，先手必胜。
异或值不为 0 时，先手必败。
只有一堆石子数大于 1，先手必胜。

先手我们可以考虑对数量大于 1 的那对堆石子下手脚，从而构造出后手必败的状态：

存在至少两堆石子数大于1
当异或和为0时，先手必败
当异或和不为0时，先手必败

证明和 Nim 游戏是相似的，可以自行证明或网上搜索，这里就不给出了。

例题：SHOI2008 小约翰的游戏

#include<bits/stdc++.h>
using namespace std;
int T,n;

void solve(){
    cin>>n;
    int ans=0;
    bool flag=0;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        ans^=x;
        if(x>1) flag=1;
    }
    if(!flag&&!ans) cout<<"John\n";
    else if(flag&&ans) cout<<"John\n";
    else cout<<"Brother\n";
}

int main(){
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

4.2 反 SG 游戏

我们根据 Anti-Nim 游戏能否推广到一般性情况呢？有的兄弟有的，反 SG 游戏就是。

我们定义：

Anti-SG游戏：决策集合为空的游戏者赢，剩下规则与 SG 游戏相同。

那么，如何判断能否赢呢？

对于 Anti-SG 游戏，如果我们规定当局面单一游戏的 $\operatorname{SG}$ 值为 0 时，游戏结束，则先手必胜当且仅当：

游戏的 $\operatorname{SG}$ 函数不为0且游戏中某个单一游戏的 $\operatorname{SG}$ 函数值大于 1。
游戏的 $\operatorname{SG}$ 函数为0且游戏中没有某个单一游戏的 $\operatorname{SG}$ 函数值大于 1。

证明和 $\operatorname{SG}$ 函数类似。

5. 博弈论及与其他知识结合

5.0 操作手册

博弈论确实可以和其他芝士一起结合起来一块考。

一般我们拿到一个看起来像是博弈论的题，我们需要确定题目的类型，可以通过几个操作手册来：

确定博弈：大部分的博弈论题都是假博弈论，有可能是贪心什么的。需要自行观察以下，尤其警惕标题带博弈论的 www。
思考模型：大部分博弈都有基础模型，我们通过基础模型来构建起问题的 “整体”，这也是为什么我们上面给出那么多的组合游戏模型。
落实限制：我们找到模型后，题目一般都会给予你几个限制。现在就是发挥你实力的时候了，通过知识点的综合运用，将模型转化到一些知识点上去。
分类讨论：这个时候就是通过限制来进行分类讨论，不做过多介绍，可以做题体会。
写代码

5.1 例题

这里举几个比较简单的例题。DP 与博弈论的考察一般考察方案数的选取，或带有特殊限制的博弈问题。或者通过 DP 来求解博弈论所需要的信息。

GZOI2017 取石子游戏

不难发现这是一个带特殊限制的 NIM 游戏。

让 Alice 必败就是让其选择的石子堆中的数量异或为 0，要么无法在这一堆中足够的石子使得剩下的异或为 0，所以给定 Alice 选择的石子数量一定要大于等于其他选择的堆的数异或值。

考虑枚举 Alice 选哪一堆，让后对于其他石子堆用 DP 求出前 $i$ 堆中任意选择一些使得异或值为 $j$ 的方案数，直接统计即可，时间复杂度 $O(n^2 \times 256)$ 。

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=520,MOD=1e9+7;
int f[MN][MN],ans,n,a[MN];

void solvedp(int x){
    memset(f,0,sizeof(f));
    f[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<256;j++){
            if(i==x) f[i][j]=f[i-1][j];
            else f[i][j]=(f[i-1][j]+f[i-1][j^a[i]])%MOD;
        }
    }
}

signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        solvedp(i);
        for(int j=a[i];j<256;j++){
            (ans+=f[n][j])%=MOD;
        }
    }
    cout<<ans;
    return 0;
}

USACO09NOV A Coin Game S

注意到是题目中的关键信息，取的硬币数和上一步取的操作有关，这个直接思考不太好，我们考虑进行 DP 求解。

设 $f(i,j)$ 表示取到第 $i$ 个金币，取金币的上限为 $j$ 先手取的最大价值，转移是显然的，考虑记忆化搜索实现比较好些，但是转移是 $O(n^3)$ 的。

考虑优化，注意到我们 $f(i,j)$ 在记忆化搜索是 $1 \rightarrow n$ 取搜索的，那么我们 $f(i,j)$ 的答案其实包含了 $f(i,j-1)$ ，那么我们可以直接搜 $f(i,j-1)$ 没有的部分，即 $(x+lim,lim\times 2)$ ，其中 $lim$ 为金币上限，那么这样搜索复杂度就是 $O(n^2)$ 的了。

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=2e3+15;
int f[MN][MN],n,s[MN],c[MN];

int dfs(int x,int y){
    y=min(y,n-x+1);
    if(~f[x][y]) return f[x][y];
    if(x+y>n) return s[x];
    if(!y) return 0;
    int ans=dfs(x,y-1);
    ans=max(ans,s[x]-dfs(x+y,y<<1));
    return f[x][y]=ans;
}

signed main(){
    cin>>n;
    memset(f,-1,sizeof(f));
    for(int i=1;i<=n;i++){
        cin>>c[i];
    }
    for(int i=n;i>=1;i--) s[i]=s[i+1]+c[i];
    cout<<dfs(1,2);
    return 0;
}

ZJOI2009 取石子游戏

神题：

再次复读：

神仙题.jpg。ZJOI 是真的神仙。
发现 SG 函数等东西完全找不到规律，无奈只能翻题解。

看 wsyhb的题解吧，他说的肯定比我好 www。

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=1520;
int L[MN][MN],R[MN][MN],n,a[MN];

void solve(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        L[i][i]=R[i][i]=a[i];
    }
    for(int len=2;len<=n;len++){
        for(int l=1;l+len-1<=n;l++){
            int r=l+len-1;
            int x=a[r],xl=L[l][r-1],xr=R[l][r-1];
            if(x==xr) L[l][r]=0;
            else if(x>=xl&&x<xr) L[l][r]=x+1;
            else if(x>xr&&x<=xl) L[l][r]=x-1;
            else L[l][r]=x;
            x=a[l],xl=L[l+1][r],xr=R[l+1][r];
            if(x==xl) R[l][r]=0;
            else if(x>=xr&&x<xl) R[l][r]=x+1;
            else if(x>xl&&x<=xr) R[l][r]=x-1;
            else R[l][r]=x;
        }
    }
    if(L[2][n]==a[1]) cout<<0<<'\n';
    else cout<<1<<'\n';
}

int main(){
    int T;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

P4363

对于这种博弈论的题，基本上理解就能想到了把状态压出来，然后做记忆化搜索。

对于落子的限制条件是，上方和左方的格子要么是棋子要么是边界。

我们可以考虑直接状压落子的状态，存每一行铺到了哪个位置，这个方法的复杂度显然为 $O(n^m)$ 的。

我们发现，一个棋子想要存在的条件是上方和左方的所有格子全部被棋子填满。

那么，对于任意时刻，棋盘上的棋子构成一个锯齿形。

那有用的情况有多少种呢，我们考虑从锯齿状的起点开始走，我们最多往右走 $n$ 步，往下走 $m$ 步，路径数论是多少？显然为 $\dbinom{n+m}{n}$ 种。

算出来就是 $184756$ 中，考虑暴力 11 进制状压，让后用 map 存就可以了。

注意开 long long。

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=15,INF=1e18;
int a[MN][MN],b[MN][MN],ed,n,m;
map<int,int> ans,vis;

int dfs(int x,int y){
    if(x==ed) return 0;
    if(vis[x]==1) return ans[x];
    vis[x]=1;
    int p=1,sum=y?INF:-INF,tmp=x;
    int c[MN]{};
    c[0]=INF;
    for(int i=1;i<=n;i++) c[i]=tmp%11,tmp/=11;
    if(y){
        for(int i=1;i<=n;i++){
            if(c[i]<min(c[i-1],m)) sum=min(sum,dfs(x+p,y^1)-b[i][c[i]+1]);
            p*=11;
        }
    }
    else {
        for(int i=1;i<=n;i++){
            if(c[i]<min(c[i-1],m)) sum=max(sum,dfs(x+p,y^1)+a[i][c[i]+1]);
            p*=11;
        }
    }
    ans[x]=sum;
    return ans[x];
}

signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>b[i][j];
        }
    }
    for(int i=1;i<=n;i++) ed=ed*11+m;
    cout<<dfs(0,0);
    return 0;
}

HNOI2010 取石头游戏

这种题的模型就是：“我可以死，但你要死的更惨！”。

由于得分之和是定值，且双方都想让自己分数最大，我们不妨令 $val$ 表示先手得分与后手得分的差，类似于对抗搜索，那么先手要让 $val$ 尽可能大，而后手尽量让 $val$ 小。

而取石子，可以转化为两端分别有一个栈，可以从栈顶取石子，中间有若干个双端队列，可以从其两端取石子。

让后我们对连续的三个元素进行分类讨论，分别有：

递增
递减
先增后减
先减后增

因为我们取的方向是从外到内的，我们接下来分类讨论。

递增：我们肯定要放到后面选择，因为一旦先手选择，后手一定能够选择比他大的数的。
递减：优先选择递减里面最大的。
先增后减与先减后增：到了这个情况的化，后手肯定选择中间的情况，先手肯定会选择左后两个。考虑证明：
- 如果先手发现选取最优的话，他会选走这个。由于先增加后减少，所以当前对于后手而言，选取比上一次最优还优秀的点肯定是最佳的，随意肯定会选中间那个。
- 若不一定最优秀，那么可能会选取其他更优的决策点。但是最终还是要选择这个剩下的点。我们直接把这个情况压成一个点的情况，这样所有的双段队列和栈就不会出现任何线增加后减少的情况了。

贪心即可：

#include<bits/stdc++.h>

#define maxn 2000010
using namespace std;
typedef long long ll;
template < typename T > inline void read(T & x) {
    x = 0;
    char c = getchar();
    bool flag = false;
    while (!isdigit(c)) {
        if (c == '-') flag = true;
        c = getchar();
    }
    while (isdigit(c)) {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    if (flag) x = -x;
}
ll n, sum, val, s, L, R, tot;
ll l[maxn], r[maxn], v[maxn];
bool tag[maxn];
bool cmp(const ll & a,
    const ll & b) {
    return a > b;
}
int main() {
    read(n), r[0] = 1, l[n + 1] = n;
    for (int i = 1; i <= n; ++i)
        read(v[i]), sum += v[i], l[i] = i - 1, r[i] = i + 1, tag[i] = (v[i] != 0);
    for (int i = 3; i <= n; i = r[i])
        while (tag[l[l[i]]] && tag[l[i]] && tag[i] && v[l[i]] >= v[l[l[i]]] && v[l[i]] >= v[i])
            v[i] = v[l[l[i]]] + v[i] - v[l[i]], r[l[l[l[i]]]] = i, l[i] = l[l[l[i]]];
    L = r[0], R = l[n + 1];
    while (v[L] >= v[r[L]] && tag[L] && tag[r[L]]) s += v[r[L]] - v[L], L = r[r[L]];
    while (v[R] >= v[l[R]] && tag[R] && tag[l[R]]) s += v[l[R]] - v[R], R = l[l[R]];
    for (int i = L; i <= R; i = r[i])
        if (tag[i])
            v[++tot] = v[i];
    sort(v + 1, v + tot + 1, cmp), v[++tot] = s;
    for (int i = 1; i <= tot; ++i) {
        if (i & 1) val += v[i];
        else val -= v[i];
    }
    printf("%lld %lld", (sum + val) / 2, (sum - val) / 2);
    return 0;
}

6. 后言

蒟蒻博弈论就学到这里了，如果还有后面的进一步学习，还是会更新内容了。

这篇文章，我感觉还是欠缺一部分 SG 解题的部分。见的题还是不太多，坑还是要补的 www。

看在这么用心的份上，不要脸的求赞 www。

博弈论半家桶——从入门到门入从

0. 前言

1. 组合博弈与博弈基础

1.1 公平组合与非公平组合

1.2 先手，后手，必胜必输局面

1.3 先手必胜与先手必败

1.4 必胜点与必败点

2. 基本公平组合游戏

2.1 Nim 游戏

2.2 Nim升级版——NimK

2.3 阶梯 Nim 游戏

2.4 巴什博弈 Bash Game

2.5 威佐夫博弈

2.6 斐波那契博弈

2.7 总结

3. SG与有向图游戏

3.1 有向图游戏

3.2 Mex 运算

3.3 SG 函数

3.4 必胜与必败判定,SG 定理

3.5 公平组合游戏为何结局注定？

3.6 NIM 游戏与 SG 函数的结合

3.7 SG例题与复杂博弈论技巧

4. 反常游戏与反SG游戏

4.1 Anti-Nim游戏

4.2 反 SG 游戏

5. 博弈论及与其他知识结合

5.0 操作手册

5.1 例题

6. 后言

参考