博弈论

zhaojiaen · 2026-03-11 21:41:05 · 算法·理论

前言

博弈论是研究决策者在特定规则和条件下如何进行策略选择的理论，其充满智慧且极具魅力。然而，在研习的过程中，我深感现有中文教材的知识脉络往往略显陈旧浅显，而网络上的文章又大多碎片化，质量良莠不齐，初学者极易陷入“知其然不知其所以然”的困境。

基于对知识规整的需要，亦为了给同好者提供一份具备系统性与深度参考价值的资料，我撰写了这篇文章。文中不仅涵盖了基础理论讲解，更融入了我对模型转换的思考。愿这份躬耕之作，能如同一份清晰的地图，帮助诸位在博弈论的纵横捭阖间，寻得一条通往真理的坦途。

本文将主要介绍尼姆游戏、威佐夫博弈、巴什游戏、SG 函数的相关变形运用及一些用搜索或者动态规划解决的博弈论问题。最后会简单讲解一下博弈树。一些不常用的博弈论知识点本文并不涉及。

在本文开始之前，我须以最诚挚的敬意感谢我的同学 zth。他在我学习期间所给予的深刻指导与无私启迪，构成了本文的核心逻辑基石，并对本文部分例题的证明逻辑性进行了建议，使例题证明过程更加完整。可以说，没有他提供的智力支持，本文的观点将难以为继。

此文章配套题单博弈论相关练习学习体验更佳。

本文篇幅较长，但旨在详尽，力求诸位在研读此篇后，无需再为寻找同类基础性或进阶性资料而费时。此作倾注良多，愿不负读者的耐心与期待。

尼姆游戏

游戏规则

有 n 堆石子，每堆有 a_i 个。两人轮流从任意一堆中取出至少一个石子，可以取光。最后取光石子的人获胜。

必胜策略

对于一个局面 (a_1, a_2, \dots, a_n)，定义 Nim_sum 为：

• 若 S \neq 0，则先手必胜。
• 若 S = 0，则先手必败。

下面来证明这种策略的正确性。

首先当所有石子都被取光时，局面是 (0, 0, \dots, 0)，此时异或和必然是 0。根据规则，谁面对这个局面谁就输了。

其次，任何 S \neq 0 的状态，都可以一步变成 S = 0 的状态。

假设当前的尼姆和 S = k \neq 0。 下面证明：一定能找到一堆石子 x_i，将其变为 x_i'，使得新的尼姆和变为 0。

1. 找到 S 的二进制表示中，最高位的 1 所在的第 d 位。
2. 在所有堆中，一定至少存在一堆 x_i，其二进制的第 d 位也是 1（否则异或结果在该位不可能为 1）。
3. 让 x_i 变成 x_i' = x_i \oplus S。这时候因为 S 的最高位 d 在 x_i 中也是 1，异或后该位变为 0，而比 d 更高的位 x_i 和 x_i' 是相同的。所以无论 d 位以下的数值如何变化，x_i' 一定小于 x_i。这意味着这一步操作是符合游戏规则的（减少石子）。
4. 这时候修改后的总异或和： S_{new} = S \oplus x_i \oplus x_i' = S \oplus x_i \oplus (x_i \oplus S) = 0

最后任何 S = 0 的状态，改变任意一堆后，其 S 必然不为 0。

假设 x_1 \oplus x_2 \oplus \dots \oplus x_i \oplus \dots \oplus x_n = 0。如果你改变了其中一堆 x_i 变为 x_i'（其中 x_i' < x_i），那么新的异或和为：

由于 x_i' \neq x_i，根据异或性质，两个不相等的数异或结果绝不会是 0。因此，S_{new} \neq 0。

现在我们形成了一个逻辑闭环：

• 如果你面对 S \neq 0：你总能通过合法操作把局面变成 S = 0 扔给对手。
• 如果你面对 S = 0：无论你怎么操作，你扔给对手的局面必然 S \neq 0。
• 最终：由于石子总数在减少，游戏必然结束。那个不断把 S=0 丢给对方的人，最终会把全 0 局势丢给对方。

因此，只要初始状态 S \neq 0，先手就有必胜策略。

模板代码

题目链接：P2197 【模板】Nim 游戏

这是一道经典模板题，这里不再赘述了。

#include <bits/stdc++.h>

using namespace std;

int T;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> T;

    while (T--)
    {
        int n, s = 0; cin >> n;

        for (int i = 1; i <= n; ++i)
        {
            int a; cin >> a;
            s ^= a;
        }

        if (s == 0) cout << "No\n";
        else cout << "Yes\n";
    }

    return 0;
}

经典变形

我们现在通过一些例题来具体讲解。

以下例题依次运用到：尼姆游戏的一般运用、反尼姆游戏、尼姆游戏在动态规划中的运用、阶梯 Nim、k-Nim、斐波那契 Nim。

\textit{\textbf {Eg1}}

题目描述：P1247 取火柴游戏

题目简述：

这道题在模板的基础上要求回答先手必赢的话第一步具体要拿多少石子。

推导过程

假设有 n 堆石子，数量分别是 a_1, a_2, \dots, a_n。

我们现在的目标是：把 a_i 变成一个新的数字 a_i'，使得所有堆新的异或和等于 0。

我们对等式左右两边同时异或上除了 a_i' 以外的所有项：

根据 X \oplus X = 0，左边的式子里，除了 a_i' 以外，全部都自己跟自己抵消了。所以等式变成了：

如果我们算出其他所有堆的异或和挺麻烦的，要遍历一遍。但我们可以发现：

两边同时异或 a_i：

结合刚才我们推的等式：

题目要求只能取石子，不能增加石子，因此我们只需要遍历一遍 a_i，看是否满足

找到第一个满足条件的就好了。

参考代码

#include <bits/stdc++.h>

using namespace std;

const int K = 500010;

int k, n[K], s;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> k;

    for (int i = 1; i <= k; ++i)
    {
        cin >> n[i];
        s ^= n[i];
    }

    if (s == 0) cout << "lose\n";
    else
    {
        for (int i = 1; i <= k; ++i)
        {
            if ((n[i] ^ s) < n[i])
            {
                int taken = n[i] - (n[i] ^ s);

                cout << taken << " " <<  i << "\n";

                n[i] = n[i] ^ s;

                for (int j = 1; j <= k; ++j) cout << n[j] << " ";

                exit(0);
            }
        }
    }

    return 0;
}

\textit{\textbf {Eg2}}

题目描述：P4279 [SHOI2008] 小约翰的游戏

我们称这种最后取完判定为输的游戏为反尼姆游戏（即 Anti-Nim）。

推导过程

看到题目描述说取出最后 1 个算输时，我们可以先想出一种特殊局面：当每一堆石子的数量都只有 1 的时候。

每一次取石子都能使一堆石子消失。

• 如果有偶数堆，最后一堆将由哥哥拿走，哥哥输。
• 如果有奇数堆，最后一堆将由小约翰拿走，小约翰输。

那么当出现这种情况时，我们只需要判断 n 的奇偶性即可。

如果石子堆中有个数大于 1 的石子堆呢？

这时候其实先手就拥有了改变游戏性质的控制权。

如果当前异或和 S \neq 0： 先手总能通过普通 Nim 策略，把局面变成 S=0 留给后手。 先手会一直维持这个策略，直到产生一种特殊情况：轮到先手时，场上只剩下一堆石子 >1，其余堆全是 1。怎么证明一定会出现这种状态呢？也很简单。

首先，如果一个局面里只有一堆石子大于 1（假设为 m），其余全是 1（假设有 k 个），那么它的异或和是：

由于 m > 1，它的二进制最高位一定比 1 高。无论后面那串 1 异或是 0 还是 1，m 的那个最高位都无法被消掉。

因此，只要场上只有一堆大于 1，异或和绝对不可能 为 0。也就是说，只要目前的异或和 S = 0，场上大于 1 的石子堆数要么是 0，要么至少是 2。

现在我们开始按照上面的情况取石子，根据 Nim 理论，一定能找到一种走法，把某一堆改掉，使得剩下的 S = 0。

正如上面证明的，既然剩下的 S=0，那么剩下的局面里，大于 1 的堆数 依然至少是 2。

哥哥无论怎么动，都会破坏平衡。他动了其中一堆，必然会导致 S \neq 0。

• 如果哥哥把其中一堆大于 1 的石子变成了 0 或 1，场上大于 1 的堆数就减 1。
• 如果哥哥只是减少了那一堆的数量但依然保持它 >1，大于 1 的堆数不变。

因此，石子堆中个数大于 1 的堆的数量一直在减小，并且由于哥哥面对的总是 S=0，他不可能把大于 1 的堆数从 2 直接变成 0，所以先手必然会遇到场上只剩下一堆石子 >1，其余堆全是 1 的情况。

这时候先手有必胜策略：

• 如果剩下的 1 有奇数个，先手就把那一堆 >1 的石子全部拿完，留给后手奇数个 1（后手必败）。
• 如果剩下的 1 有偶数个，先手就把那一堆 >1 的石子拿得只剩 1 个，留给后手奇数个 1（后手必败）。

而当异或和 S=0 时，这种控制权就到了哥哥手里，所以先手必败。

以上推导就是反尼姆游戏的必胜策略。

• 如果所有堆的石子数都为 1：堆数为偶数则先手胜，奇数则先手败。
• 如果存在至少一堆石子数 > 1：总异或和 S \neq 0 则先手胜，S = 0 则先手败。

参考代码

#include <bits/stdc++.h>

using namespace std;

int T, n;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> T;

    while (T--)
    {
        cin >> n;

        int cnt = 0, s = 0;

        for (int i = 1; i <= n; ++i) 
        {
            int a; cin >> a;
            s ^= a;
            if (a > 1) cnt++;
        }

        if (cnt == 0)
        {
            if (n % 2 == 0) cout << "John\n";
            else cout << "Brother\n";
        }
        else
        {
            if (s == 0) cout << "Brother\n";
            else cout << "John\n";
        }
    }

    return 0;
}

\textit{\textbf {Eg3}}

题目链接：P5675 [GZOI2017] 取石子游戏

推导过程

题目要求：算出有多少种方案让 Alice 不能获胜。Alice 第一步必须取第 i 堆。Alice 想赢，她就会在第一步把局面变成一个必败局面丢给 Bob。

那么什么时候 Alice 不能取胜呢？我们很容易发现，对于选定的一组石子堆，如果 Alice 无论从第 i 堆取走多少个石子，都无法让剩下的石子异或和变为 0，那么 Alice 就输了。那么我们现在的问题就变成了考虑什么时候 Alice 无法让剩下的石子异或和为 0。

设选出的其他石子的异或和为 S'，第 i 堆石子数为 a_i。

根据 Nim 游戏结论，Alice 想要获胜，必须把 a_i 变成 a_i'，使得 a_i' \oplus S' = 0，即 a_i' = S'。

因为 Alice 只能取走石子，所以必须满足 a_i' < a_i。也就是说，只要 S' \ge a_i，Alice 就没法通过动第 i 堆来获胜。

因此，我们只需要统计方案数：对于每一个指定的 i，在剩下的 N-1 堆中选出若干堆，使得它们的异或和 S' \ge a_i。

参考代码

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int MOD = 1e9 + 7;
const int N = 210;
const int MAX = 260;

int n;
int a[N];
ll dp[N][MAX], ans;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n;

    for (int i = 1; i <= n; ++i) cin >> a[i];

    for (int i = 1; i <= n; ++i) // 枚举必须第一次操作的那一堆
    {
        memset(dp, 0, sizeof dp);
        dp[0][0] = 1;

        int cnt = 0;

        for (int k = 1; k <= n; ++k)
        {
            if (k == i) continue;

            cnt++;

            for (int j = 0; j < MAX; ++j)
            {
                dp[cnt][j] = (dp[cnt][j] + dp[cnt - 1][j]) % MOD;
                dp[cnt][(j ^ a[k])] = (dp[cnt][(j ^ a[k])] + dp[cnt - 1][j]) % MOD;
            }
        }

        for (int s = 0; s < MAX; ++s)
        {
            if (s >= a[i])
            {
                ans = (ans + dp[cnt][s]) % MOD;
            }
        }
    }

    cout << ans << "\n";

    return 0;
}

\textit{\textbf {Eg4}}

题目链接：P3480 [POI 2009] KAM-Pebbles

在讲解这道题之前，先给大家讲解一下什么是阶梯 Nim。

游戏规则：假设有一座 n 层的阶梯，每层编号为 1, 2, \dots, n。地面记为 0 号阶梯。每层阶梯上放有若干个石子，第 i 层有 a_i 个。

两名玩家轮流操作：选择第 i 层（i \ge 1）的任意数量（至少 1 个）石子，移动到第 i-1 层。

移动到第 0 层（地面）的石子就相当于被移出了游戏。

无法进行操作的人输（即最后拿光的人赢）。

必胜策略：

阶梯 Nim 中整个游戏的胜负仅取决于所有奇数号阶梯上石子数量的异或和。

• 如果 a_1 \oplus a_3 \oplus a_5 \oplus \dots \neq 0，则先手必胜；
• 如果奇数号阶梯上的石子异或和为 0，则先手必败。

证明：

定义 S = \{a_1, a_2, \dots, a_n\}，其中 a_i 是第 i 层的石子数。令 X = a_1 \oplus a_3 \oplus a_5 \oplus \dots（所有奇数下标层的异或和）。

首先，当所有石子都移动到第 0 层时，游戏结束。此时 a_1=a_3=\dots=0，因此 X = 0。根据规则，此时面对该局面的玩家无法操作，判定为输。

显然，当 X \neq 0 时，一定存在一种移动方式使 X = 0。这与 Nim 游戏证明一致，这里不再赘述。

其次，当 X = 0 时，无论如何移动，下一步的 X 一定 \neq 0。证明如下：

这里需要分两种情况讨论对手的操作：

• 对手移动了奇数层 i 的石子到偶数层 i-1：

  这种操作改变了奇数层 i 的石子数量（a_i \to a_i'）。在异或运算中，改变其中一个操作数，结果必然改变。所以新的异或和 X' = X \oplus a_i \oplus a_i' \neq 0。根据标准 Nim 游戏的理论，一定能找到一种合法的移动方式，把某个奇数层石子再移走一部分，使得异或和重新回到 0。

• 对手移动了偶数层 j 的石子到奇数层 j-1：

  这种操作增加了奇数层 j-1 的石子数量（a_{j-1} \to a_{j-1} + k）。此时奇数层的异或和 X 会从 0 变为 0 \oplus (a_{j-1} \oplus (a_{j-1} + k))，显然这也不等于 0。面对这种情况，只需要把对方刚刚移入奇数层 j-1 的那 k 个石子，继续向下移动到偶数层 j-2。这样，奇数层 j-1 的石子数又变回了 a_{j-1}，异或和 X 重新回到 0。

所以当异或和不为 0 时，不管后手怎么操作，先手总能把状态控制到异或和为 0 的局面，直到石子的数量全为 0。所以先手必胜。如果开始时异或和不为 0，局面的控制权就变到了后手手里，所以先手必败。

模板代码：

#include <bits/stdc++.h>

using namespace std;

int n, s;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n;

    for (int i = 1; i <= n; ++i)
    {
        int a; cin >> a;
        if (i % 2 != 0) s ^= a;
    }

    if (s == 0) cout << "first\n";
    else cout << "second\n";

    return 0;
}

现在我们回到这道题。我们发现这与模板有所不同。

推导过程

题目规定：每次从第 i 堆拿走一些石子后，依然要满足 a_{i-1} \le a_i \le a_{i+1}。

这意味着第 i 堆能拿走的石子上限，取决于它前一堆的数量 a_{i-1}。

我们构造一个差分序列 d：满足 d_i = a_i - a_{i-1}，特别的，d_1 = a_1。

根据题目条件 a_i \ge a_{i-1}，可以得出 d_i \ge 0。

当我们从第 i 堆拿走 k 个石子时，可以发现：

可以发现，这就是阶梯 Nim，只不过是倒序阶梯。

现在这道题就解决了。具体操作请看代码。

参考代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int u, n;
int d[N], a[N], s;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> u;

    while (u--)
    {
        cin >> n;

        for (int i = 1; i <= n; ++i)
        {
            cin >> a[i];
            d[i] = a[i] - a[i - 1];
        }

        s = 0;

        for (int i = 1; i <= n; ++i)
        {
            if (i % 2 != 0) s ^= d[n - i + 1];
        }

        if (s != 0) cout << "TAK\n";
        else cout << "NIE\n";
    }

    return 0;
}

\textit{\textbf {Eg5}}

题目链接：P2490 [SDOI2011] 黑白棋

在讲这道题之前，先介绍一下 k-Nim（又称 Moore's Nim）。

k-Nim 的游戏规则是这样的：

有若干堆石子，两名玩家轮流操作。

在每次操作中，玩家可以选择至少 1 堆，至多 k 堆物品，并从这些被选中的堆中各取走任意正整数个物品（不同堆取走的数量可以不同）。

取走最后一个物品的玩家获胜。

可以发现，这是个广义的尼姆游戏。

这个游戏的必胜策略是：

假设有 m 堆物品，数量分别为 N_1, N_2, \dots, N_m。

将每个 N_i 写成二进制表示。对于二进制的每一位（列）j，将所有堆在这一位上的数字（0 或 1）相加，得到列和 c_j。

• 如果对于所有的列 j，都有 c_j \equiv 0 \pmod{k+1}，那么当先手必败。
• 只要有任何一列的列和 c_j \not\equiv 0 \pmod{k+1}，则先手必胜。

下面我们来简短的证明这个必胜策略。

首先对于结束状态，当所有堆为 0 时，s_j 显然全部为 0，即终局是必败态。

假设现在是先手操作，当前局面所有位均为 0\pmod{k+1}，则一次操作至多改变 k 堆，对于任意一位 i，该位上为 1 的堆数 c_i 的变化量不超过 k。故不可能仍为 0 \pmod{k+1}。

这时候该后手操作，设最高一位 d 满足 c_d \not\equiv 0 \pmod{k+1}，记 c_d \equiv m\ (1\le m\le k)。取 m 个第 d 位为 1 的堆，每堆减去 2^d，则第 d 位变为 0 \pmod{k+1}。再在这至多 k 堆内适当减少低位（总量小于 2^d），即可同时将所有低位调整为 0 \pmod{k+1}。一直如此操作直到所有位均为 0，此时先手无法操作，因此先手必败。

当先手的局面为存在至少一列的列和 c_j \not\equiv 0 \pmod{k+1}，先手可以进行上述后手的操作，把局面控制权互换，如此操作相当于上述情况先手、后手角色互换，因此先手必胜。

推导过程

我们观察游戏规则：白色棋子只能向右，黑色只能向左，且不能互相跨越。并且因为 k 是偶数，所以棋子是成对出现的。

每一对棋子之间的距离（格子数）记为 g_i。当玩家移动白色棋子向右或黑色棋子向左时，距离 g_i 都会减小。

这本质上是一个有 m = k/2 堆石子的 Nim 游戏，每堆石子的数量就是 g_i。

题目规定每次可以移动 1 到 d 个棋子。由于移动同一对中的两个棋子没有意义（相当于只操作了一堆石子），且题目允许操作不同的棋子，这等价于：每次可以从最多 d 堆石子中取走任意数量的石子。

可以发现，这就是我们上面提到的 k-Nim。

我们要计算小 A 胜利的方案数。直接计算比较困难，我们正难则反，可以先计算小 B 胜的方案数，然后用总方案数减去它。

既然让求方案数，肯定跟动态规划脱不了干系。我们考虑怎么定义状态并进行转移。

我们需要求出满足以下条件的序列 (g_1, g_2, \dots, g_m) 的数量：

• 对于任意二进制位 j，设有 c_j 个 g_i 在第 j 位为 1，则 c_j \equiv 0 \pmod{d+1}。

根据上面关于 k-Nim 的学习很容易想到状态定义：设 f_{i,j} 表示已经处理完前 i 个二进制位，当前石子总和为 j 的小 A 必败方案数。

现在我们考虑状态转移。

这个状态转移很容易理解。下面来稍微解释一下，根据 k-Nim 结论，若想让小 A 必败，则每一位上 1 的个数必须是 (d+1) 的倍数。因此石子总和要是 d + 1 的倍数。在第 i 位上产生的贡献为 2^i。

其中：

现在我们通过 DP 算出来了有多少种整数序列 (g_1, g_2, \dots, g_m)，满足 k-Nim 的必败条件，且它们的总和 \sum g_i = S。但是每种情况里棋子内部的摆放方案并没有计算。我们现在考虑如何计算。

棋子占了 k 个格子。m 对棋子内部的空格总数是 S。剩余的空格数是 n - k - S。

这些剩余的空格可以放在：第一对左边、两对之间、或者最后一对右边。

总共有 m+1 个空隙可以放。这是一个经典的隔板法问题：将 n-k-S 个无区别的空格放入 m+1 个有区别的槽位。方案数为：

把 m=k/2 代入，得到：

必败态总数就为：

其中，maxbit 为处理到的最高位。

因此，小 A 胜利方案数：

最后注意，当我们什么都没处理的时候，方案只有一种，即 f_{0,0}=0。

具体细节请看代码。

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int MOD = 1e9 + 7;
const int N = 1e4 + 1;
const int MAX = 20;

int n, k, d;
ll fact[N], infact[N];
ll f[MAX][N];

inline ll qmi(ll a, ll b)
{
    ll res = 1;

    while (b)
    {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }

    return res;
}

inline void init()
{
    fact[0] = infact[0] = 1;

    for (int i = 1; i < N; ++i)
    {
        fact[i] = fact[i - 1] * i % MOD;
        infact[i] = infact[i - 1] * qmi(i, MOD - 2) % MOD;
    }
}

inline ll C(int n, int m)
{
    if (m < 0 || n < m) return 0;
    return fact[n] * infact[n - m] % MOD * infact[m] % MOD;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n >> k >> d;

    init();

    int m = k / 2;
    f[0][0] = 1;

    int maxbit = 14; // 因为 2^14 > 10000

    for (int i = 0; i <= maxbit; ++i)
    {
        for (int j = 0; j <= n - k; ++j)
        {
            if (f[i][j] == 0) continue; // 剪枝，值为 0 下面的计算肯定也是 0，就不用浪费时间再计算了。

            for (int p = 0; p * (d + 1) <= m; ++p)
            {
                int count = p * (d + 1);
                int nxtsum = j + count * (1 << i);

                if (nxtsum > n - k) break;

                f[i + 1][nxtsum] = (f[i + 1][nxtsum] + f[i][j] * C(m, count) % MOD) % MOD;
            }
        }
    }

    ll total = 0;

    for (int s = 0; s <= n - k; ++s)
    {
        if (f[maxbit + 1][s] == 0) continue;

        ll ways = f[maxbit + 1][s] * C(n - s - m, m) % MOD; 

        total = (total + ways) % MOD;
    }

    ll ans = (C(n, k) - total + MOD) % MOD;

    cout << ans << endl;

    return 0;
}

\textit{\textbf {Eg6}}

由于目前洛谷上还没有关于此知识点的题目，这里就只介绍一下算法。

我们来介绍一下斐波那契 Nim。

游戏规则是这样的：

有一堆石子，共计 n 枚。两名玩家轮流取石子。第一个行动的玩家不限制取走的石子数目，但是不能取完石子；随后，每次取走的石子数目不得超过上次（指对手回合）取走的石子数目的二倍。每次取走的石子的数目不得为 0。取走最后一枚石子的玩家获胜。

必胜策略：

当且仅当初始石子数 n 不为斐波那契数时，先手必胜。

在斐波那契博弈中，有一堆数量为 n 的石子。第一回合，先手可以取走任意数量 k（1 \le k < n）个石子。随后，每一回合玩家取走的石子数 k' 必须满足 1 \le k' \le 2m，其中 m 是上一回合取走的石子数。取走最后一颗石子的人获胜。

其核心结论是：当且仅当 n 不是斐波那契数时，先手必胜。

下面我们来证明这个必胜策略。

齐肯多夫定理

要证明此博弈，必须依赖齐肯多夫定理：任何正整数 n 都可以唯一地表示为若干个互不相邻的斐波那契数之和。

即：n = \sum_{j=1}^k F_{i_j}，其中 i_j \ge i_{j+1} + 2，且 i_k \ge 2。

证明：

1. 存在性：使用数学归纳法。对于 n=1,2,3 显然成立。假设对于所有小于 n 的整数成立。设 F_m 是不大于 n 的最大斐波那契数。若 n=F_m，结论成立；若 n > F_m，令 n' = n - F_m。由于 F_m \le n < F_{m+1}，则 n' < F_{m+1} - F_m = F_{m-1}。根据归纳假设，n' 可表示为不相邻斐波那契数之和，且其最大项必定小于 F_{m-1}，因此 F_m 与 n' 的分解项不相邻。
2. 唯一性：利用斐波那契数列的性质 \sum_{i=0}^{k} F_{2i+1} = F_{2k+2} 和 \sum_{i=1}^{k} F_{2i} = F_{2k+1}-1，可以证明任何不相邻项的和都严格小于更高位的下一项斐波那契数，从而保证了表示法的唯一。

斐波那契博弈的构造性证明

我们将 n 表示为齐肯多夫和：n = F_{i_1} + F_{i_2} + \dots + F_{i_k}，其中 i_1 > i_2 > \dots > i_k \ge 2。

1. 若 n 不是斐波那契数（k > 1），先手必胜。

先手第一次取走最小的齐肯多夫分量 F_{i_k}。

根据齐肯多夫定理的性质，由于相邻两项不连续，必有 i_{k-1} \ge i_k + 2。

由斐波那契递推式可知：

这意味着，先手取走 F_{i_k} 后，后手面对剩下的石子堆，其首项分量为 F_{i_{k-1}}，但后手最多只能取 2F_{i_k} 个石子，无法一次性取走下一个分量 F_{i_{k-1}}。

先手可以通过不断地取每个齐肯多夫分量的末尾，确保自己总能取走每个 F_{i_j} 块的最后一颗石子，最终获胜。

2. 若 n 是斐波那契数（k = 1），后手必胜。

设 n = F_i。先手第一次取走 k 个石子。

• 若 k \ge \frac{1}{3} F_i，后手在某些情况下可能直接取完，但更严谨的逻辑是：如果先手取走的 k 使得剩下的 F_i - k 的最小齐肯多夫分量 F_m 满足 2k \ge F_m，则后手可以进入上述“先手必胜”的逻辑。
• 通过齐肯多夫分解可以证明，对于任何 k < F_i，在剩下的石子中，最小的齐肯多夫分量 F_m 满足 F_m \le 2k。我们来简单证明一下这个引理：设 k 的齐肯多夫分解最小项为 F_j。若先手取走 k 个，剩余 F_i - k。可以证明 F_i - k 的齐肯多夫分解中，最小项 F_m 一定满足 F_m \le 2k。这意味着无论先手怎么取，后手总能根据齐肯多夫分解拿走剩余部分的最小分量，掌握主动权。

威佐夫博弈

游戏规则

有两堆物品，数量分别为 a 和 b。两位玩家轮流进行以下两种操作之一：

• 从其中一堆中取走任意数量的物品（至少取 1 个）。
• 从两堆中同时取走相同数量的物品（每堆都至少取 1 个）。

取走最后一个物品的人获胜（让对手面临 (0, 0) 的玩家获胜）。

必胜策略

在博弈论中，让先手必败的局面称为奇异局势。我们用 (a_n, b_n) 表示第 n 个奇异局势（假设 a_n \le b_n）：

• n=0: (0, 0)
• n=1: (1, 2)
• n=2: (3, 5)
• n=3: (4, 7)
• n=4: (6, 10)
• n=5: (8, 13)

运用我们超绝洞察力可以发现规律：

那么随着 n 的增加，局势中的所有数值将会覆盖自然数集。

威佐夫博弈的结论为：

如果满足

则先手必败。

下面给出证明。

这个结论基于贝蒂定理：

若两个正无理数 \alpha, \beta 满足：

则序列 A = \{\lfloor n\alpha \rfloor\} 和 B = \{\lfloor n\beta \rfloor\} (n \in \mathbb{Z}^+) 会不重不漏地覆盖所有正整数。

这个定理我们在证明完威佐夫博弈的必胜策略后给大家证明。

我们求解是否能找到奇异局势的通项公式。

由于随着 n 的增加，奇异局势中的所有数值将会覆盖自然数集，所以设 a_n = \lfloor n\alpha \rfloor，b_n = \lfloor n\beta \rfloor，代入 b_n = a_n + n 得：

这个过程看起来很自然，然我还是想要严谨的证明一下为什么能直接去掉取整符号。

为此，我专门请教了 zth，他从极限的角度出发证明了这一过程。在他的口胡和我的精简总结下形成了以下证明：

利用高斯符号的性质，对于任何整数 k，都有 \lfloor x \rfloor + k = \lfloor x + k \rfloor。

由于 n 是整数，我们可以将 n 移进括号内：

整理提取公因子 n：

为了去掉 \lfloor \rfloor 符号，我们利用高斯符号的基本定义 x - 1 < \lfloor x \rfloor \le x。

对于上述等式，意味着 n\beta 与 n(\alpha + 1) 的取整结果必须严格一致。

从反证法的角度出发，假设 \beta \neq \alpha + 1，设其差值为 \Delta = \beta - (\alpha + 1)。则有：

• 如果 \Delta > 0，随着 n 的增大，n\Delta 总会达到并超过 1。当 n\Delta \ge 1 时，\lfloor n(\alpha + 1) + n\Delta \rfloor 至少会比 \lfloor n(\alpha + 1) \rfloor 大 1，导致原等式失效。
• 如果 \Delta < 0，同理，当 n 足够大使得 n\Delta \le -1 时，等式也会失效。

因此， n\beta = n\alpha + n。

我们现在继续证明。

我们把等式 \beta = \alpha + 1 代入 \frac{1}{\alpha} + \frac{1}{\alpha + 1} = 1，整理得：

解方程（取正根）得 \alpha = \frac{1+\sqrt{5}}{2}。

现在，我们求出了奇异局势的通项公式，也就找出了先手的必胜策略。

现在，我们转回头来简单证明一下贝蒂定理：

我们需要证明：当 \frac{1}{\alpha} + \frac{1}{\beta} = 1 且 \alpha, \beta 为正无理数时，序列 A = \{\lfloor n\alpha \rfloor\} 和 B = \{\lfloor n\beta \rfloor\} (n \in \mathbb{Z}^+) 不重不漏地覆盖了所有正整数。

对于任意正整数 m，我们计算序列 A 和 B 中小于或等于 m 的项数之和。

在序列 A 中，满足 \lfloor n\alpha \rfloor \le m 的项数：

因为 n 是正整数，所以项数为满足上述条件的 n 的最大取值。

由于 \alpha 是无理数，\frac{m+1}{\alpha} 不可能是整数，因此项数为：

同理，在序列 B 中，小于或等于 m 的项数为：

将这两个项数相加，记总项数为 S(m) = N_A(m) + N_B(m) = \lfloor \frac{m}{\alpha} \rfloor + \lfloor \frac{m}{\beta} \rfloor。

利用高斯符号性质 x-1 < \lfloor x \rfloor < x（注意，因为是无理数，取不到等号）：

1. 左侧不等式：

   \frac{m}{\alpha} - 1 + \frac{m}{\beta} - 1 < S(m) m(\frac{1}{\alpha} + \frac{1}{\beta}) - 2 < S(m)

   由于 \frac{1}{\alpha} + \frac{1}{\beta} = 1，得：m - 2 < S(m)。

2. 右侧不等式：

   S(m) < \frac{m}{\alpha} + \frac{m}{\beta}

   得：S(m) < m。

结合这两个不等式，对于任何整数 m，都有：

因为 S(m) 必须是整数，在这个区间内唯一的整数就是：

我们接着来证明其不遗漏性：

当 m 变为 m+1 时，总项数 S(m+1) = (m+1) - 1 = m。

这意味着从数字 m 到 m+1，总共只增加了一个新项（要么来自序列 A，要么来自序列 B）。这保证了没有正整数被漏掉。

最后，我们来证明其不重复性：

如果序列 A 和 B 中存在相同的数，即 \lfloor n_1\alpha \rfloor = \lfloor n_2\beta \rfloor = k。

那么在计算 S(k) 时，这个 k 会被计算两次，即 S(k) - S(k-1) 应该等于 2。

但根据上面的证明，S(k) - S(k-1) = (k-1) - (k-2) = 1。

这说明每个整数只增加了一次，从而证明了序列 A 和 B 没有交集。

证明完毕。

下面给出威佐夫博弈的模板代码。

模板代码

题目链接：P2252 【模板】威佐夫博弈 / [SHOI2002] 取石子游戏

#include <bits/stdc++.h>

using namespace std;

int a, b;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> a >> b;

    if (a > b) swap(a, b);

    long double phi = (sqrtl(5) + 1.0) / 2.0;

    int n = b - a;

    if (a == (long long)(n * phi)) cout << "0\n";
    else cout << "1\n";

    return 0;
}

值得说明的是，由于精度限制，这道题需要使用 sqrtl 而并非 sqrt。

经典变形

其实威佐夫博弈用的并不多（因为洛谷上关于此的题就很少，亦或者可以说目前并没有），所以在这里只介绍一种变形，其他的变形则需要打表找规律或者较为复杂。

k-威佐夫博弈：

规则变为：从一堆中取任意个，或从两堆中同时取，但两堆所取数量的差的绝对值不能超过 k-1。

在这种情况下，奇异局势的差值不再是 n，而是 kn。

利用我们之前推导出的公式：

• 差值要求：b_n = a_n + kn \implies \beta = \alpha + k
• 划分要求：\frac{1}{\alpha} + \frac{1}{\beta} = 1

联立解得：\alpha^2 + (k-2)\alpha - (k-1) = 0。根据求根公式，取正根：

巴什游戏

游戏规则

只有一堆物品，数量为 n。两人轮流从这堆物品中取物，规定每次至少取 1 个，最多取 m 个。最后取光物品的人获胜。

必胜策略

• 若 n \pmod{m+1} \neq 0，则先手必胜。
• 若 n \pmod{m+1} = 0，则先手必败。

这个结论很好理解，下面给出先手必胜的简要证明。

如果 n = q(m+1) + r（其中 r \neq 0）： 先手第一次取走 r 个。之后无论对手取走 k 个（1 \le k \le m），先手只要取走 m+1-k 个，就能保证剩下的石子始终是 m+1 的倍数。最终，先手一定能取到最后一批。

其实和尼姆游戏的策略很像，都是把游戏的控制权握在自己手里，不管对方怎么取，先手都能保证局势不变，最后取胜。

模板代码过于简单，这里就不再给出了。下面给出一道相似的题。

题目链接：P4018 Roy&October之取石子

推导过程：

• 如果 n = 1 \sim 5，都存在 p^k = n，可以一次拿完，先手赢。
• 当 n = 6 时，不存在 p^k = 6，先手只能拿 1 \sim 5 个，后手赢。
• 如果 n 不为 6 的倍数，设 n=6q+r，0 < r < 6，先手只需要第一次取 r，这时候局面的控制权就在先手的掌握中，情况和上面相同，此时先手必胜。

因此，如果 n 是 6 的倍数，后手赢。否则，先手赢。

考虑到文章篇幅，代码不再给出。

经典变形

巴什游戏最重要的方法就是找规律，通过模数来控制游戏。下面给出一道分析题（虽然此题和巴什游戏没有太大关系，但其体现的思想是一致的）。

题目链接：P4101 [HEOI2014] 人人尽说江南好

推导过程

游戏规则是将两堆石子合并，且合并后每堆不能超过 m。 当所有石子都尽可能地合并到了上限 m 时，游戏就结束了。

我们可以发现，不管两人怎么操作，堆数每次都减少 1，我们要让每一堆大小都尽量逼近 m，因为无论你怎么合并，最终大家的目标都是把石子堆到尽量接近 m。即便某种合并方式留下了几个小堆，只要小堆之和 \le m，聪明的玩家为了延长或缩短游戏步数，最终都会将其合并。所以会剩下 \lceil n / m \rceil 堆，需要合并 R = n - \lceil n / m \rceil 堆 （即需要走的步数）。

关于剩下的堆数是否绝对等于 \lceil n / m \rceil 的证明，在 zth 同学的质疑下，我对此进行了思考，并想出了一个不太严谨的证明。至于 zth 同学，他想出了一个看起来很严谨的证明，但由于和我的证明大同小异，故在此只说明一下我的证法。

首先，在游戏还没有开始之前，两人按照最理想的状态能推算出自己的胜负。这里假设先手胜。后手为了破坏这个理想的状态，就会使剩余堆数改变。

在双方均采取最优策略的条件下，尽管后手可能试图通过制造大小介于 (m/2, m) 之间的非饱和堆来人为增加终局堆数、从而缩减总步数，但这种破坏意图在实际博弈中是无法实现的。

由于合并权在双方之间交替且对称，每当后手尝试构建一个无法与他堆合并的孤立状态时，先手作为拥有预见性的博弈方，必然会利用场上尚存的大量单位石子作为调节资源，抢在后手完成干扰布局前，通过后续回合强制将该堆填充至逼近 m 的饱和状态。

这种方法确保了任何试图制造局部冗余空间的尝试都会被对等的操作抵消。因此，合并过程产生的总步数并不取决于中间的分配路径，最终必然收敛于全局最小堆数所对应的步数奇偶性。

回归本题，我们只需要判断 R 的奇偶性。

• 如果 R 是奇数：先手走最后一步，先手胜。
• 如果 R 是偶数：后手走最后一步，后手胜。

参考代码

#include <bits/stdc++.h>

using namespace std;

int T;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> T;

    while (T--)
    {
        int n, m; cin >> n >> m;
        int r = n - (n - 1) / m + 1;
        cout << (r % 2 == 0 ? "1\n" : "0\n");
    }

    return 0;
}

P - postion & N - postion

概念

• P-position (Previous player wins)：

  直译为“上一个玩家获胜”。即代表着当前局面当前选手必败（必败态）。

• N-position (Next player wins)：

  直译为“下一个玩家获胜”。既代表着当前局面如果当前选手采取最优解则必胜（必胜态）。

所有的博弈分析都建立在以下三个递推准则中。

1. 无法进行任何合法操作的局面是必输态。因为规则一般定义“走不动的人输”。当选手站在 0 （终点）或者走不动的状态时必输。
2. 如果一个状态可以通过一步操作到达任何一个必败态，那么这个状态就是必胜态。因为只要能把对手送进必败的局面，当前选手就是必胜的。
3. 如果从一个状态出发，所有可能的合法操作都会指向必胜态，那么这个状态就是必败态。因为不管当前选手怎么挣扎，当前选手这一步走完，对手都会面对一个必胜态。那当前选手显然就是死路一条。

当题目满足是公平博弈，只有单一局面，游戏能在有限步数内结束时，可以考虑用 P - postion & N - postion 完成。

下面给出一道例题，来更加深入理解这个知识点。

例题讲解

题目链接：P2953 [USACO09OPEN] Cow Digit Game S

推导过程

很容易可以看出这道题可以用博弈论必胜态必败态解决。我们考虑状态推导。

很容易可以想到我们定义令 f_i 表示数字为 i 时，当前操作者的胜负情况。

对于当前的数字 n，设其最大数码为 max\_digit，最小非零数码为 min\_digit。如果存在一种走法（减去 max\_digit 或 min\_digit）能让下一个状态变成必败态，那么当前状态就是必胜态。

公式表达：f_n = (f_{n - max\_digit} == 0) \lor (f_{n - min\_digit} == 0)。

边界条件：f_0 = 0（因为减到 0 的人已经操作完了，轮到下一个人时数字为 0，无法操作，所以下一个人必败）。

这道题其实并不难，状态的定义首先就很容易想出来，题目说的已经很明白了，剩下的只需要照着题目说的模拟就好了。

参考代码

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1000010;

int G;
bool win[MAXN]; 

inline void get(int n, int &maxd, int &mind)
{
    maxd = 0;
    mind = 9;

    int temp = n;

    while (temp > 0)
    {
        int d = temp % 10;
        temp /= 10;
        if (d > maxd) maxd = d;
        if (d > 0 && d < mind) mind = d;
    }
}

inline void prepare()
{
    win[0] = false;

    for (int i = 1; i < MAXN; ++i)
    {
        int maxd, mind;

        get(i, maxd, mind);

        if (win[i - maxd] == false || win[i - mind] == false)
        {
            win[i] = true;
        }
        else
        {
            win[i] = false;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    prepare();

    cin >> G;

    while (G--)
    {
        int n; cin >> n;

        if (win[n]) cout << "YES" << endl;
        else cout << "NO" << endl;
    }

    return 0;
}

图游戏

定义

一个图游戏可以定义为一个有向图 G = (V, E)，其中：

在两人、轮流行动、信息完全的规则下，博弈从某个初始节点 v_0 开始。

判定

根据博弈的终止条件和图的结构（是否存在环），状态被严谨地划分为必胜态、必败态和平局态。

在大多数图游戏中，遵循“最后移动者获胜”的准则。此时，终止状态，即出度为 0 的节点（F(u) = \emptyset），被定义为必败态。

设 S 为所有状态的集合，我们将 S 划分为三个互斥的子集：N、P 和 D。

1. 必胜态：状态 u \in N，当且仅当存在至少一个后继状态 v \in F(u)，使得 v 是必败态。

   \exists v \in F(u), \text{ s.t. } v \in P

2. 必败态：状态 u \in P，u 不是终止状态时，当且仅当对于所有的后继状态 v \in F(u)，v 都是必胜态。

   \forall v \in F(u), \text{ s.t. } v \in N

   注：根据定义，若 F(u) = \emptyset，则 u \in P。其中 \text{s.t.} 是英文 such that 的缩写，中文意思是“使得”。

3. 平局态：状态 u \in D，当且仅当 u \notin N 且 u \notin P。这意味着：不存在任何后继状态 v \in P（否则 u 将成为 N）。至少存在一个后继状态 v \in D。平局通常发生在包含环的图中，玩家可以无限循环移动以避免进入必败态

状态转移

1. 将所有出度为 0 的节点标定为 P。其余节点状态未知。

2. 若节点 u 尚未标定，且其后继节点中至少有一个被标定为 P，则将 u 标定为 N。 若节点 u 尚未标定，且其后继节点全部被标定为 N，则将 u 标定为 P。

3. 重复执行步骤 2，直到没有新的节点可以被标定。

4. 迭代结束后，仍未被标定的节点（即无法在有限步内推导至终止状态的节点）即为平局态。

很多树形 DP 或记忆化搜索处理博弈题，其本质就是在图游戏上做逆向拓扑递推。

SG 函数

概念

SG 函数是解决博弈论问题的一个强有力的工具。

SG 函数真正的巧妙是通过题去感受的，冗余的介绍会增加学者的学习难度。因此这里直接给出 SG 函数的基本定义。

首先，你需要知道：MEX(S) 表示集合 S 中未出现的最小非负整数。

对于状态 x，它的 SG 值定义为：

其中 y 是从状态 x 出发，通过一次合法操作能到达的所有后继状态。

规则

• 终结局面：无法移动的状态（如棋子到终点），SG = 0。
• P-position (必败态)：若 SG(x) = 0，则当前玩家必败。
• N-position (必胜态)：若 SG(x) > 0，则当前玩家必胜（因为他一定能走到一个 SG=0 的状态）。

必胜策略

当一个大游戏由 n 个相互独立的子游戏组成时（例如有 n 堆石子，每次只能选一堆玩），并且为双人轮流制，无随机因素，游戏状态和规则完全公开的时候，这个游戏通常可以用 SG 函数解决，整个游戏的 SG 值等于各子游戏 SG 值的异或和：

我们先来证明一下 SG 定理：SG_{total} = SG(G_1) \oplus SG(G_2) \oplus \dots \oplus SG(G_n)。

假设我们有一个复合游戏 G，它由 n 个独立的子游戏 G_1, G_2, \dots, G_n 组成。当前的状态是 x = (x_1, x_2, \dots, x_n)。

令这 n 个子游戏当前状态的 SG 值异或和为 s。

我们现在的最终目标，就是证明整个游戏状态 x 的 SG 值也等于 s，即 SG(x) = s。根据 \text{mex} 的定义，要证明 SG(x) = s，我们只需要证明以下两件事：

1. 能到更小：对于任意一个非负整数 a < s，我们都能通过一步合法操作，把当前状态变成一个 SG 值为 a 的新状态。
2. 不到自己：我们绝不可能通过一步合法操作，把当前状态变成一个 SG 值仍为 s 的新状态。

只要这两点成立，最小的无法到达的非负整数就必然是 s，定理也就得证了。

我们先来证明第一步：假设有一个目标值 a，且 a < s。我们要证明总能找到一种走法让新状态的异或和变成 a。

我们令 d = s \oplus a。因为 a < s，所以在 s 和 a 的二进制表示中，从高位往低位比，出现不同的第一位一定是 s 为 1，而 a 为 0。这就意味着，d 的最高位（设为第 k 位）必然是 1。

现在我们转回头看 s 是怎么来的：s = SG(x_1) \oplus SG(x_2) \oplus \dots \oplus SG(x_n)。

既然 s 的第 k 位是 1，那么在这 n 个子游戏中，必然存在至少一个子游戏 G_i，它的当前状态的 SG(x_i) 在第 k 位也是 1。

由于 SG(x_i) 的第 k 位是 1，而 d 的最高位也是第 k 位，那么当我们将它们相异或时，因为最高位从 1 变成了 0，值肯定变小了，即：

根据 SG 函数的 \text{mex} 定义，既然 SG(x_i) \oplus d 是一个小于 SG(x_i) 的非负整数，那么在子游戏 G_i 中，必然存在一步合法的操作，能把状态 x_i 变成一个新状态 y_i，使得：

现在，我们在整个复合游戏中执行这一步操作：只动子游戏 G_i，把 x_i 变成 y_i，其他子游戏不动。

此时，整个新状态 y = (x_1, \dots, y_i, \dots, x_n) 的 SG 值异或和为：

又因为 d = s \oplus a，所以：

下面我们来证明第二步，即无论在这 n 个子游戏里怎么选，只要是合法操作，都不可能走到一个 SG 值依然是 s 的状态。

假设存在这样一步操作，我们选择在子游戏 G_i 中，把状态 x_i 变成 y_i（其中 x_i \neq y_i）。

假设新状态的 SG 值异或和仍然等于 s。

我们有：

两边同时异或 s，得到：

即：

但是，这违反了 SG 函数的定义。根据定义：

既然 x_i 能一步走到 y_i，那么 y_i 的 SG 值就已经出现在了 x_i 的后续状态集合里。而 \text{mex} 选的是未出现的数。

所以，SG(x_i) 绝不可能等于它后继状态 SG(y_i) 的值。

证明完毕。

SG 函数的应用前提是游戏必须属于公平组合博弈。这类博弈的一个核心特征是：游戏必须在有限步内结束。

如果博弈图中存在环，玩家就可以在环路中无限循环移动。这种情况下，游戏无法满足“有限步结束”的定义，导致状态的 SG 值出现递归死循环，无法通过运算得出确定的非负整数。

因此，只有在有向无环图上，我们才能通过拓扑序向上地推导出每个节点的 SG 值。

我们通常使用记忆化搜索来计算 SG 函数。

由于洛谷上并没有 SG 函数的模板题，下面我们从一道相对简单的题引出。

例题

\textit{\textbf {Eg1}}

题目链接：P2575 高手过招

推导过程

我们可以发现，棋子只能向右移动，所以每行棋盘就相当于一个个独立的游戏，这显然符合 SG 函数的特征，考虑用 SG 函数解决。

既然各行互不干扰，我们只需要研究一行棋盘怎么算。 我们把一行的 20 个格子看成一个长度为 20 的序列。

每一格只有“有”和“无”两种状态，这适合用二进制表示。

题目链接：P10501 Cutting Game

题目简述

给定一个 W \times H 的矩形，两名玩家轮流选取一个纸片横向或者纵向切割，谁切出 1 \times 1 谁赢。

推导过程

在切割过程中，会产生若干张大小不同的纸片，我们可以把每张纸片当成一个独立的游戏，可以发现这道题和 SG 函数相适配。

但 SG 函数常规定义中，通常是无法操作的人输。我们需要将规则等价的转换一下。

如果一个矩形可以被切成 1 \times 1，那么当前操作者直接获胜。换句话说， 1 \times 2，1 \times 3，2 \times 1，3 \times 1 这些状态是必胜态的直接来源。为了方便计算，我们可以将 2 \times 2，2 \times 3，3 \times 2 定义成这个游戏的终点，因为在这个状态下不论怎么切割下个选手都能切出 1 \times 1 的网格纸片。

下面我们考虑如何计算 SG 值。

当你切一刀时，原本的一个游戏变成了两个相互独立的子游戏。根据 SG 定理：

其中，SG(W, i) \oplus SG(W, H-i) 是指横切时的 SG 值等于横切后两个独立的纸片的 SG 值的异或和。SG(j, H) \oplus SG(W-j, H) 是指竖切时的 SG 值等于竖切后两个独立制片的 SG 值的异或和。i，j 分别代表横切和竖切的位置。

边界限制：

为了不切出 1 \times n 或 n \times 1 这种直接让对手赢的局面，我们的切割必须满足：

• 横切：i \ge 2 且 H-i \ge 2。
• 纵切：j \ge 2 且 W-j \ge 2。

结束状态：如果一个矩形无论如何都切不出两个面积大于等于 2 \times 2 的矩形，那么它就是当前的必败态（SG 值为 0）。

由对称性考虑到局面 (W,H) 和 (H, W) 是等价的，我们可以在计算的过程中减少计算，具体详见代码。

参考代码

#include <bits/stdc++.h>

using namespace std;

const int MAX = 210;

int w, h;
int sg[MAX][MAX];

int getsg(int w, int h)
{
    if (w > h) swap(w, h);
    if (sg[w][h] != -1) return sg[w][h];

    bool vis[MAX << 1];
    memset(vis, false, sizeof vis);

    for (int i = 2; i <= w - i; ++i)
    {
        vis[getsg(i, h) ^ getsg(w - i, h)] = true;
    }

    for (int i = 2; i <= h - i; ++i)
    {
        vis[getsg(w, i) ^ getsg(w, h - i)] = true;
    }

    int res = 0;

    while (vis[res]) res++;

    return sg[w][h] = res;
}

int main()
{
    memset(sg, -1, sizeof sg);

    while (~scanf("%d %d", &w, &h))
    {
        if (getsg(w, h) > 0) cout << "WIN\n";
        else cout << "LOSE\n";
    }

    return 0;
}

\textit{\textbf {Eg3}}

题目链接：P8369 [POI 2000] 条纹

题目简述

这个题的规则有些饶，通俗的讲就是可以在棋盘中任意连续空格位置放置条纹。

推导过程

每放一个条纹，就相当于把一个连续的棋盘切成了两个更短的、相互独立的子棋盘。

可以发现，当棋盘被条纹隔开后，左边的操作完全不影响右边，所以这个游戏具有独立性。

并且游戏结束规则是走不动的输，符合标准的 SG 函数定义。

总局面的 SG 值等于所有剩余空段 SG 值的异或和。

因此，这道题可以考虑用 SG 函数解决。

我们首先考虑如何定义 SG 函数。

可以发现，一段连续的空格就是一个独立的游戏。因此这个游戏的胜负性质就只由他长度决定，因此我们定义：SG_i 为长度为 i 的连续空格的 SG 值。

考虑状态转移。

我们可以枚举使用把哪一条条纹放到棋盘上。

很容易可以想到转移：

其中，j 是条纹左边留下的空格数。

由于这道题的询问较多，并且棋盘最大长度较小，我们可以考虑离线处理。

剩下的细节请看代码。

#include <bits/stdc++.h>

using namespace std;

const int P = 1010;

int c, z, n, m;
int sg[P];
int vis[P];
int times;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> c >> z >> n;

    memset(sg, 0, sizeof sg); // 默认是必输的状态

    int l[3] = {c, z, n};

    for (int len = 1; len <= 1000; ++len)
    {
        times++;

        for (int k = 0; k < 3; ++k)
        {
            if (len >= l[k])
            {
                for (int j = 0; j <= len - l[k]; ++j) // 枚举放完条纹后左边剩下的空格长度
                {
                    int val = sg[j] ^ sg[len - l[k] - j];
                    vis[val] = times;
                }
            }
        }

        int res = 0;
        while (vis[res] == times) res++;
        sg[len] = res;
    }

    cin >> m;

    while (m--)
    {
        int p; cin >> p;
        if (sg[p] == 0) cout << "2\n";
        else cout << "1\n";
    }

    return 0;
}

\textit{\textbf {Eg4}}

题目链接：P3179 [HAOI2015] 数组游戏

推导过程

首先，从判断是否有必胜策略可以看出来这是一道博弈论的题。

题目规定每次选择一个白色棋子进行操作，如果无法找到白色棋子进行操作就输了。这提示我们应该围绕白子展开操作。

并且，因为操作是独立的，我们可以将每个白子当成一个独立游戏。

以上两点符合 SG 函数的定义，可以考虑用 SG 函数解决。根据 SG 定理，整个局面的 SG 值等于所有白格 SG 值的异或和。如果异或和不为 0，则先手必胜。

下面我们考虑如何推导 SG 函数。

设白格位置为 x，每次能选择的 k 范围是 1 \le k \le \lfloor n/x \rfloor。

翻转后，x 变黑，相当于消除了 x 处的白格；而 2x, 3x, \dots, kx 的颜色发生翻转。

因此，单步操作转移后的 SG 值为 \bigoplus_{j=2}^k SG(j \times x)。

可以看出，位置 x 的 SG 值其实只与 m = \lfloor n/x \rfloor 有关。令 g(m) 表示剩余可操作倍数为 m 时的 SG 值，则：

当 k=1 时，异或和为 0。

由于 n \le 10^9，直接按上述公式计算需要 O(m)，整体复杂度过高。注意到 \lfloor m/j \rfloor 在一段区间 [L, R] 内是恒定不变的。我们可以考虑整除分块。这样，我们可以将求单点 SG 值的复杂度从 O(m) 降到 O(\sqrt{m})。

下面来简单介绍一下整除分块。

如果我们要计算

我们可以发现 \lfloor n/i \rfloor 的值在一段连续的区间内是不变的。

我们想到可以把这些相同的块一次性算出来，就可以降低一定的复杂度。

假设当前块的左端点是 l，我们需要找到最大的右端点 r，使得对于所有 i \in [l, r]，\lfloor n/i \rfloor 都相等。这个 r 的计算公式极其简洁：

证明（简述）： 设 k = \lfloor n/l \rfloor。我们要找最大的 r 满足 r \cdot k \le n，显然 r \le n/k。向下取整即得 r = \lfloor n/k \rfloor。

参考代码

    long long ans = 0;

    for (int l = 1, r; l <= n; l = r + 1)
    {
        r = n / (n / l);
        // 当前块的值是 n/l，块的长度是 (r - l + 1)
        ans += (long long)(r - l + 1) * (n / l);
    }

回归本题，由于 n 过大，我么可以考虑用两个数组 sg_1，sg_2 来分开存储 SG 值。

• 对于 \le \sqrt{n} 的 m，存在 sg_1 中；
• 对于 > \sqrt{n} 的 m，存在 sg_2 中。

剩下的实现就很套路了，具体实现细节请看代码。

参考代码

#include <bits/stdc++.h>

using namespace std;

const int MAX = 5e4 + 10;

int n, query;
int divide,sg1[MAX], sg2[MAX];

int getsg(int m)
{
    if (m == 0) return 0;

    int &memo = (m <= divide ? sg1[m] : sg2[n / m]);
    if (memo != -1) return memo;

    bool vis[200]; //数组用来记录当前状态能转移到的所有后继状态的 SG 值
    memset(vis, false, sizeof vis);

    vis[0] = true; // 当只翻转自身（k=1) 时，没有后续的其他白格产生，异或和为 0。所以 0 这个后继状态是可以达到的。

    int cur = 0; //cur 用来记录在枚举 k 的过程中，前面所有块累积下来的前缀异或和。

    for (int l = 2, r; l <= m; l = r + 1) // k 从 2 开始枚举，因为 k=1 已经特判了。
    {
        r = m / (m / l);

        int val = getsg(m / l);

        vis[cur ^ val] = true; //只要进入了循环，就说明当前至少还有一个合法的 k 可以选，
                               //即 k=L 是一个客观存在的选项，那么 cur ^ val 就一定是一个可达的状态。

        if (r > l) vis[cur] = true; //只要这个块的长度 >= 2，那么 k 一定有机会包含偶数个 val。
                                    // 偶数个 val 异或抵消了，所以后继状态还是之前的 cur。
        if ((r - l + 1) % 2 == 1) cur ^= val; //如果当前块有奇数个元素，那对后续的总异或和会多出一个 val 的影响；
                                              //偶数个则全部抵消，没有影响。
    }

    int mex = 0;

    while (vis[mex]) mex++;

    return memo = mex;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n >> query;

    divide = sqrt(n) + 1;

    memset(sg1, -1, sizeof sg1); memset(sg2, -1, sizeof sg2);

    while (query--)
    {
        int w; cin >> w;

        int total = 0;

        for (int i = 1; i <= w; ++i)
        {
            int idx; cin >> idx;
            total ^= getsg(n / idx);
        }

        if (total == 0) cout << "No\n";
        else cout << "Yes\n";
    }

    return 0;
}

说明

这道题的代码其实并不难写，难的是抽离出游戏模型和 SG 函数状态的表达，剩下整除分块优化和存储优化则相对来说比较好想。

其他博弈论问题

介绍

有些博弈论问题，我们可能无法使用以上游戏进行完成。这时候一般需要我们打表找规律，或者结合动态规划、搜索完成。下面通过几道例题让大家来熟悉一下这类问题。

例题

\textit{\textbf {Eg1}}

题目链接：P4363 [九省联考 2018] 一双木棋 chess

说个题外话，这是我接触的第一道博弈论相关题目，它被放在了模拟赛的第一题。当时我并不了解博弈论，也没有想到能用搜索完成博弈论问题，就写了个假贪心，哪知道还能骗到 35 分。正是因为赛后想要补这道题并且考虑到现在比赛考察思维是大趋势，由此萌生了学习博弈论并且整理成文章的想法。

推导过程

首先读完题看到数据范围我们可以发现这道题多半可以用状压 DP 或者搜索完成。

通过模拟样例可以发现棋盘的有效落子区域必然是左上角的一个阶梯形。

这里提供的一个做法是我们可以用一条从左下角到右上角的轮廓线来表示当前盘面，即表示这个阶梯型的外围。

用 1 表示向上走，用 0 表示向右走。

棋盘大小为 n \times m，那么轮廓线总共需要走 n 步向上和 m 步向右，因此可以用一个长度为 n+m 且包含正好 n 个 1 的二进制数来表示所有的合法状态。

首先考虑起始状态可以发现是先走 n 步上，再走 m 步右。二进制表示为低位连续 n 个 1，值为 2^n-1。

再考虑最终状态可以发现是先走 m 步右，再走 n 步上。二进制表示为高位连续 n 个 1，值为 (2^n-1) \times 2^m，即初始状态左移 m 位。

现在我们考虑哪些区域可以落子，落子后的状态转移是什么？

我们通过规则“一个格子可以落子当且仅当这个格子内没有棋子且这个格子的左侧及上方的所有格子内都有棋子。”可以发现：在轮廓线上，如果有一个向上的步紧接着一个向右的步（二进制中表现为低位 1，高位 0），这对应着一个“凹角”，也就是当前可以落子的位置。

落子后，这个“先上后右”的凹角就变成了“先右后上”的凸角（即把状态表示中的 10 替换成 01，用异或操作即可实现）。

那我们怎么判断当前的执棋人是谁？

我们可以计算当前二进制中 1 的位置总和，减去初始状态 1 的位置总和，就是当前已经落子的个数。

偶数个为先手（菲菲，求差值的最大值），奇数个为后手（牛牛，求差值的最小值）。

这道题涵盖了轮廓线 DP （其实也是状压 DP）的运用，由于此知识点不在本文讲解范畴内，故这里不再阐述，感兴趣的读者可以下去自行查阅资料。

如果你感觉似懂非懂，请看下面代码，相信能让你了解的更透彻一些。

参考代码

#include <bits/stdc++.h>

using namespace std;

const int N = 11;
const int M = 11;
const int MAX = (1 << 20) + 10;
const int INF = 1e9;

int n, m;
int a[N][M], b[N][M];

// f：记录状态的最优差值
// vis: 记录状态是否被访问过
int f[MAX];
bool vis[MAX];

int dfs(int state)
{
    if (vis[state]) return f[state];

    if (state == ((1 << n) - 1) << m) return 0; // 终止状态，游戏结束，不再产生分数

    vis[state] = true;

    // 统计 1 的位置下标之和

    int cnt = 0;

    for (int i = 0; i < n + m; ++i) 
    {
        if ((state >> i) & 1) cnt += i;
    }

    // 初始状态 1 的位置下标之和为 (n - 1) * n / 2

    int turn = (cnt - n * (n - 1) / 2) % 2;

    // 通过棋子数量判断奇偶性从而判断现在是谁在执棋

    int res = (turn == 0 ? -INF : INF);

    // x：走过的 1 的数量（向上的步数）
    // y：走过的 0 的数量（向右的步数）

    int x = 0, y = 0;

    // 寻找轮廓线上的凹角

    for (int i = 0; i < n + m - 1; ++i)
    {
        int now = (state >> i) & 1;
        int nxt = (state >> (i + 1)) & 1;

        if (now == 1 && nxt == 0)
        {
            // 3 = 11，和 10 异或完刚好变成 01
            int nowstate = state ^ (3 << i);

            // 计算落子的位置
            int row = n - 1 - x, col = y;

            int val = dfs(nowstate);

            if (turn == 0) 
            {
                if (val + a[row][col] > res) res = val + a[row][col];
            }
            else
            {
                if (val - b[row][col] < res) res = val - b[row][col];
            }
        }

        if (now == 1) x++;
        else y++;
    }

    return f[state] = res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n >> m;

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j) cin >> a[i][j];
    }

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j) cin >> b[i][j];
    }

    cout << dfs((1 << n) - 1);

    return 0;
}

\textit{\textbf {Eg2}}

题目链接：P2148 [SDOI2009] E&D

推导过程

这道题虽然给出的难度标签不算特别高，但是我感觉这是一道较难的题，我也不能保证我的讲解方法很自然，只能是尽力让大家更好的理解，明白每一步是怎么想的。

首先看到数据范围，多测加上每堆石子数量都异常的大。普通的推导过程肯定是过不去的，需要优化。这里我们想想忽略掉数据范围这道题怎么写。

题目给出 2n 堆石子，两两一组。每组石子的操作是独立的，且操作后只影响该组内的石子数量。这符合 SG 函数的特征，根据 SG 定理，总游戏的 SG 值等于各组 SG 值的异或和。

下面我们考虑 SG 函数的转移。

设一组石子的数量为 (x, y)。根据规则，我们可以将 x 移走，把 y 分成 a+b=y；或者移走 y，把 x 分成 a+b=x。

这个式子我认为没有什么操作空间，很难优化。因此 我们可以先通过打表打出来一小部分的数据来观察是否有规律。

先给出暴力代码。

#include <bits/stdc++.h>

using namespace std;

int sg[105][105]; 

int getsg(int x, int y) 
{
    if (sg[x][y] != -1) return sg[x][y];
    if (x == 1 && y == 1) return sg[x][y] = 0;

    set <int> s;

    for (int i = 1; i < y; i++) s.insert(getsg(i, y - i));
    for (int i = 1; i < x; i++) s.insert(getsg(i, x - i));

    int mex = 0;
    while (s.count(res)) mex++;
    return sg[x][y] = mex;
}

int main() 
{
    memset(sg, -1, sizeof sg);

    printf("   ");

    for (int j = 1; j <= 10; j++) printf("%2d ", j);

    printf("\n");

    for (int i = 1; i <= 10; i++) 
    {
        printf("%2d|", i);

        for (int j = 1; j <= 10; j++) 
        {
            printf("%2d ", sg(i, j));
        }

        printf("\n");
    }

    return 0;
}

打表的结果：

我们把第一行提出来。但是发现找不到什么规律，只觉得 SG 的值有些规律。

运用我们的超绝洞察力可以想到局面 (1,1) 是结束局面，这有些看的难受，因此我们应当设置个偏移量，把局面变成 (a-1,b-1)。

我们再把第一行的 SG 值变成二进制的形式，去和 b-1 对应。

观察一下，可以惊奇的发现 SG 的值为 b-1 末尾连续 1 的个数。

既然第一行满足这个条件，那后面的几行应该都会满足类似的条件。

我们再次观察表格，可以发现有些不同的局面却有着相同的 SG 值，这启发我们想到 SG 值可能不依赖 a，b 本身，而是依赖两者的合并信息。

由于我们把 b 进行了偏移，理所应当对 a 也进行偏移。我们对偏移后的局面进行一些操作。我们经过加法、异或、取最值等各种操作，最后可以发现或操作满足打表内容。

因此，SG 值等于 (a-1) | (b-1) 末尾连续 1 的个数。

这样我们就对 SG 的计算复杂度进行了质的提升。

参考代码

#include <bits/stdc++.h>

using namespace std;

int T;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> T;

    while (T--)
    {
        int n, ans = 0; cin >> n;

        for (int i = 0; i < n / 2; ++i)
        {
            int x, y; cin >> x >> y;

            int val = (x - 1) | (y - 1);
            int cnt = 0;

            while (val & 1)
            {
                cnt++;
                val >>= 1;
            }

            ans ^= cnt;
        }

        if (ans) cout << "YES\n";
        else cout << "NO\n";
    }

    return 0;
}

\textit{\textbf {Eg3}}

题目链接：P2964 [USACO09NOV] A Coin Game S

推导过程

首先，可以发现这是一道 DP 题。

当我们取走前面的硬币时，剩余硬币的编号一直在变。为了定义状态，我们可能需要记录当前取到了第几个硬币，这会导致下标处理起来比较繁琐。因此，我们可以倒着看硬币，又或者说是统计硬币的后缀和。状态 i 就代表距离最后一个硬币还剩多少多少硬币。这样，无论前面取了多少次，最后剩下的 i 个硬币总是序列中最后的那一部分。后缀和我们用 sum_i 表示，这样从剩余的 i 个硬币中取出 x 个获得的价值就是 sum_i-sum_{i-x}。

我们定义状态 f_{i,j}：当还剩下 i 个硬币，且当前玩家最多能取 j 个硬币时，该玩家能获得的最大价值。这里的 j 对应题目中的 k \times 2。

下面我们考虑状态转移。

假设当前玩家决定取 x 个硬币 (1 \le x \le j)。

这时候他拿到了当前这 x 个硬币的价值，剩余硬币数量变为 i - x，而对手下一轮最多可以取 x \times 2 个硬币，这时对方在剩余局面下的最优收益是