企业官网建设流程全解析

1. 这类问题的本质：先搞清楚游戏规则再谈博弈

第一次接触取石子游戏，是在一场校赛的签到题上。题目描述很简单：一堆石子，两个人轮流拿，每次可以拿1到3颗，拿到最后一颗的人赢。当时我还在用DFS硬搜状态，结果数据范围直接给到 10^9，当场傻眼。后来才知道，这种题目背后是一整套系统的博弈论解法，而且它的变体几乎覆盖了算法竞赛里所有入门级的组合博弈问题。

所谓的取石子游戏，核心就几个要素：一堆或多堆石子、每回合可操作的拿取范围、胜负判定条件（通常是谁拿完谁赢，也有反过来的“拿走最后一颗的人输”）。一旦把这些规则抽象出来，你会发现它本质上是一个状态转移问题——当前局面是“必胜”还是“必败”，只取决于它是否能转移到对方的“必败”局面。这个思路和动态规划很像，但不同的是博弈双方都在做最优决策，所以你推的是“双方都足够聪明”的前提下，先手能不能赢。

这类问题适合谁来学？一个是正在准备算法竞赛的选手，模板题几乎必出；另一个是想打牢算法基础、准备大厂面试的开发者，因为博弈论能很好地考察一个人对状态抽象和规律归纳的敏感度。哪怕你不搞竞赛，理解这一套必胜态和必败态的推理方式，对日后设计决策类算法也有帮助。

这篇总结里，我会把三个最经典的取石子模型——巴什博弈、尼姆博弈、威佐夫博弈——从头到尾拆一遍，再从它们身上抽出通用的SG函数理论，最后附上可以直接抄的C++模板和踩坑经验。看完之后，你再遇到“取石子”三个字，心里应该有底了。

2. 先把概念说透：必胜态、必败态和状态转移

2.1 一个简单的“胜负手”推导过程

先拿最简单的情况练手：一堆石子，共 n 颗，双方轮流取，每次取 1 到 3 颗。我们不用急着背结论，先从最小状态往前推。

如果当前剩下的石子数用 n 表示，游戏规则是无法取石子的人输（也就是取到最后一颗的赢）。那么：

• n = 0：轮到谁谁就输了，所以这是必败态；
• n = 1、2、3：当前玩家直接全取走，对手面对 n = 0，必败，所以这些都是必胜态；
• n = 4：当前玩家只能取 1、2、3 颗，把局面交给对手时，对手面对的分别是 n = 3、2、1，全是对手的必胜态，因此 n = 4 是必败态；
• n = 5、6、7：当前玩家可以取 1、2、3 颗，把局面交成 n = 4，让对手面对必败态，所以这几个都是必胜态；
• n = 8：又如法炮制，取 1、2、3 都只会让对手面对必胜态，所以必败。

看到规律了没有？n 对 4 取模，等于 0 的时候必败，否则必胜。这里的“4”就是“每次最多取 3 颗 + 1”得到的。这个推导过程，本质上就是博弈树的状态枚举，只不过我们用递推代替了每一层的搜索。

2.2 必胜态与必败态的递归定义

把上面这个过程抽象成通用定义：

• 一个状态是必败态，当且仅当它所有可达的状态都是必胜态；
• 一个状态是必胜态，当且仅当它至少存在一个可达状态是必败态。

这个定义看似简单，但它把“双方最优”这个博弈的前提落到了实处。你不需要真的去模拟对方的每一步棋，只需要确信：只要我能把局面交给一个必败态，那么无论对手怎么走，我都有办法继续把他拖回必败态，直到终局。

这也解释了为什么博弈问题的代码通常很短，关键却在找规律。很多新手看到网上几行代码就解出题，误以为博弈论就是背结论，其实所有结论背后都是这个状态转移推导出来的。所谓“先手必胜”和“先手必败”，都只是在整个状态图上沿着最优策略走出来的结果。

3. 三大经典取石子模型：从巴什博弈到尼姆博弈

3.1 巴什博弈（Bash Game）：最基础的一次取上限模型

巴什博弈的规则就是上面我们推过的那个：一堆石子 n 颗，双方轮流取，每次至少取 1 颗、最多取 m 颗，取到最后一颗的人赢。

结论很简洁：

• 若 n % (m + 1) == 0，则先手必败；
• 否则先手必胜。

为什么是 m + 1？因为无论对手取 x 颗（1 ≤ x ≤ m），你都可以补上 (m + 1 - x) 颗，让连续两回合的总取走数恰好是 m + 1。这样一来，只要一开始把局面的余数部分控制好，你就能始终把握节奏。这个“凑 m+1”的思路，是很多变形题的内核。

实际做题时，巴什博弈不会只给你这么裸的规则。常见变换包括：

• 取石子的人可以先取任意数量的“手续费”，这种题本质上还是巴什，只需要提前判断一下优劣；
• 石子堆是环形的、取完某一颗后整堆消失，这时候问题可能变成别的模型；
• 规定“取走最后一颗的人输”，这种叫反巴什博弈，结论也有一个很工整的变体：当 n % (m + 1) == 1 时先手必败，否则必胜，需要单独记忆。

我建议在学习阶段把巴什博弈的原型和反型放在一起对比着推导一遍，因为它们几乎是同一棵博弈树，只是终局判定的叶子节点反了一下。

3.2 尼姆博弈（Nim Game）：异或运算的优雅解法

尼姆博弈把石子从“一堆”变成“多堆”。规则是：有若干堆石子，每堆数量已知，双方轮流操作，每次只能从其中一堆里取出任意正整数颗石子，取走最后一颗的人获胜。

这个问题看起来一下子复杂了，但实际上它拥有一个极其简洁的判定条件：把所有堆的石子数做按位异或（XOR），设结果为 XOR_sum：

• 如果 XOR_sum == 0，则先手必败；
• 否则先手必胜。

我第一次看到这个结论时，觉得很不可思议，为什么异或能刻画一个多堆博弈的胜负？后来动手推了几组例子才想通：异或为 0 的状态，无论你怎么动其中一堆，都会把它变成非 0 状态；而异或非 0 的状态，一定可以通过调整某一堆的石子数，把它变回 0。这就完全对应上了我们前面“必胜态可以转移到必败态，必败态所有转移都是必胜态”的定义。

具体操作上，如果你的目标是取胜而不是只判定胜负，那么当你面对一个必胜局面（异或非 0）时，需要找到应该在哪一堆拿多少。设总异或值为 s，遍历每一堆，看 a[i] 的二进制中，是否存在一个方案让某堆变成 a[i]'，使得新的异或值为 0。简单做法是找 s 的最高位，在所有该位为 1 的堆里选一堆，令 a[i]' = a[i] ^ s。由于 s 不为 0，a[i]' 一定小于 a[i]，所以操作合法。这一步在输出方案的题目里是标准的套路。

3.3 威佐夫博弈（Wythoff Game）：黄金分割比在算法里的用武之地

威佐夫博弈又是另一种规则：有两堆石子，双方轮流操作，每次可以从任意一堆里取任意正整数颗，或者从两堆里同时取出相同数量的石子，取完所有石子的人获胜。用 (a, b) 表示两堆的数量，这里假设 a ≤ b。

它的结论和前面两个都不太一样，引入了无理数比例。判定方式是计算差值 k = b - a，然后判断是否存在一个整数 t，使得：

a == floor(t * (1 + sqrt(5)) / 2) 且 b == a + t

这里的 (1 + sqrt(5)) / 2 就是黄金分割比 φ。如果满足这个条件，说明当前局面是一个“奇异局面”，先手必败；否则先手必胜。

这个结论的推导过程比较长，核心在于所有奇异局面之间满足一种递推关系：第 t 个奇异局面的第一个数恰好是 floor(t * φ)，第二个数是第一个数加上 t。前几个奇异局面是 (0, 0)、(1, 2)、(3, 5)、(4, 7)、(6, 10)、(8, 13)……你可以自己验算一下，这些局面之间刚好覆盖了所有非负整数，并且互不重复。

实战中，威佐夫博弈的坑主要在精度。因为要用到浮点数运算，如果直接写 a == (int)((b - a) * (1 + sqrt(5)) / 2)，可能会因为浮点误差在边界数据上出错。稳妥的做法是用 long double 计算，或者两边同时平方，或者把判定改成：

tmp = (long long)((b - a) * (sqrt(5) + 1) / 2)

然后判断 if (tmp == a)。同时要在计算前保留足够高的精度常数，不要现场用 float 算 sqrt(5)。

4. 找到套路的总钥匙：SG函数与多个独立游戏

4.1 为什么需要SG函数

前面三个模型，结论都很优雅，但问题来了：如果规则不是“取 1 到 m 颗”，而是“只能取一个给定集合里的数量，比如只能取 2 的幂次颗”，或者“有 N 堆石子，每次可以从任意 k 堆中各取 1 颗”，前面那些公式还能用吗？

答案是：很多都不能直接用。这时候就要请出博弈论里最常用的通用工具——SG函数（Sprague-Grundy 函数）。它的核心思想是：把每一个局面映射成一个非负整数，这个数能统一描述“这个局面是必胜还是必败”，还能支持多个独立子局面的组合。

SG 函数的定义是：对于一个局面，设它能直接转移到的所有局面的 SG 值构成的集合为 S，那么这个局面的 SG 值就是不在 S 中的最小非负整数（mex）。特别地，没有后继状态的终局 SG 值为 0。

这个定义和我们前面说的必胜/必败判定有什么关系？关系很简单：

• SG 值为 0 的状态是必败态；
• SG 值大于 0 的状态是必胜态。

因为 SG 值为 0 意味着它所有后继的 SG 值都不为 0（即后继全是必胜态），这正好命中必败态的定义。

4.2 多个独立子局面的组合：SG 异或定理

SG 函数最漂亮的地方在于，它可以处理多个互不干扰的游戏同时进行的组合。比如取石子问题里有 3 堆石子，每堆都是一个独立的“子游戏”，玩家的每一步只影响其中一个子游戏，那么整个局面的 SG 值，就是所有子游戏 SG 值的异或。

这个结论叫 Sprague-Grundy 定理。判定方式变成了：

• 所有子游戏 SG 值的异或结果 XOR_sum == 0，则当前局面必败；
• 否则必胜。

你看，这和尼姆博弈的结论形式完全一致。其实尼姆博弈本身就是 SG 函数的一个特例：一堆石子数量为 x，允许取任意正整数颗时，这堆石子的 SG 值就是 x，异或起来自然得到尼姆结论。

这套理论的价值在于，面对很多看似毫无规律的取石子变体，你只需要搞清楚“单堆在给定规则下的 SG 值如何计算”，然后套异或定理，就能解决多堆的复合问题。所以算法竞赛里，SG 函数题的解体思路通常分两步走：先算单个局面的 SG 值，再用异或组合起来。

4.3 计算 SG 值的两种方式：暴力递推与找循环节

直接按定义计算 SG 值，可以用 DFS 加记忆化搜索。对于石子数量 n 不超过几千、每次拿取选择数量较少的情况，这个办法已经够用。但数据范围一旦到 10^9，直接算肯定超时。

好在取石子类游戏的 SG 值一般具有周期性或规律性。比如每次只能取 1、3、4 颗的规则，可以先把前几十项 SG 值列出来，用肉眼或者程序找循环节，然后直接把 n 对循环节取模再查表。

我在做这类题时有一个习惯：先把小范围 n（比如 0 到 100）的 SG 值全部打表，然后观察模式。如果发现有固定循环，就大胆优化成 O(1) 判断；如果没有循环，再考虑题目是否存在更特殊的结构。打表找规律不是歪门邪道，反而是竞赛中非常高效的务实手段，很多看起来高深的博弈结论最初都是这样发现的。

5. 代码模板与实操细节：从会推到能写对

5.1 巴什博弈的一行判定

#include <bits/stdc++.h> using namespace std; int main() { int n, m; cin >> n >> m; // n 颗石子，每次取 1~m 颗 if (n % (m + 1) == 0) cout << "先手必败\n"; else cout << "先手必胜\n"; return 0; }

这段代码几乎不需要解释，但请注意它的前置条件：每人至少取 1 颗，且取最后一颗的人赢。如果题目改成“取最后一颗的人输”，判定式要换成 n % (m + 1) == 1。建议平时就把这两种情况做成两个小函数，被反复调用。

5.2 尼姆博弈完整流程

#include <bits/stdc++.h> using namespace std; int main() { int N; cin >> N; vector<int> a(N); int xorsum = 0; for (int i = 0; i < N; i++) { cin >> a[i]; xorsum ^= a[i]; } if (xorsum == 0) { cout << "先手必败\n"; } else { cout << "先手必胜\n"; // 如果要输出走法，找到应该操作的一堆和应该变成的数 for (int i = 0; i < N; i++) { int target = a[i] ^ xorsum; // 让这堆变成 target if (target < a[i]) { cout << "从第 " << i + 1 << " 堆取走 " << a[i] - target << " 颗，剩下 " << target << " 颗\n"; break; } } } return 0; }

这里的关键在于 target = a[i] ^ xorsum 这一步。你可能会有疑问：为什么这样做完异或和会变成 0？因为原异或和是 xorsum，当我们把 a[i] 替换成 a[i] ^ xorsum 时，新的异或和等于 xorsum ^ a[i] ^ (a[i] ^ xorsum)，先抵消 a[i]，再抵消 xorsum，结果一定为 0。同时因为 target < a[i] 保证了操作合法。

5.3 威佐夫博弈的精度处理

#include <bits/stdc++.h> using namespace std; int main() { long long a, b; cin >> a >> b; if (a > b) swap(a, b); long long k = b - a; long double phi = (sqrtl(5.0L) + 1.0L) / 2.0L; long long tmp = (long long)((long double)k * phi); if (tmp == a) cout << "先手必败\n"; else cout << "先手必胜\n"; return 0; }

我强调过精度问题，这里用 sqrtl 和 long double 是为了把边界误差尽量往后推。实际比赛中数据范围如果到 10^18，这种浮点写法仍然可能翻车。更稳的替代方案是用高精度整数开方后的平方来比较判断，也就是把“是否存在整数 t 满足 a == floor(t * phi)”转成一个二次方程的整数判定。不过竞赛中大部分题目数据不会那么极端，long double 已经能通过。

5.4 SG 函数通用模板

#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; int sg[MAXN]; bool vis[MAXN]; vector<int> moves; // 每次允许取的数量 int dfsSG(int x) { if (sg[x] != -1) return sg[x]; vector<int> reachable; for (int v : moves) { if (x >= v) { reachable.push_back(dfsSG(x - v)); } } int g = 0; while (true) { bool found = false; for (int r : reachable) { if (r == g) { found = true; break; } } if (!found) break; g++; } return sg[x] = g; } int main() { int n; cin >> n; // 石子总数 int m; cin >> m; // 可选拿取方式的数量 moves.resize(m); for (int i = 0; i < m; i++) cin >> moves[i]; memset(sg, -1, sizeof(sg)); sg[0] = 0; dfsSG(n); // 求单堆 n 的 SG 值 cout << sg[n] << "\n"; // 非 0 则先手必胜 return 0; }

这个模板定义了“从当前石子数转移到当前石子数减去某个允许值”的单堆博弈。注意 vis 数组其实可以省掉，因为这里只求最小值，直接用一个 vector 收集后继 SG 值后再遍历即可。如果要处理多堆，只需要把每一堆的 SG 值异或起来。实际做题时，moves 和题意强相关，比如“每次只能取 2 的幂次颗”，那么 moves = {1, 2, 4, 8, ...}，要先用循环把允许的操作集合生成出来，再跑模板。

5.5 我的实战代码组织习惯

比赛时博弈题的代码通常不长，但我会刻意把三类模型和 SG 模板封装成函数，而不是全写在 main 里。这个习惯有过一次救了我：有一道题是综合题，前半部分是一堆单石子巴什博弈，后半部分是多堆尼姆博弈，场景混在一起，如果都堆在 main 里，调试的时候极容易把变量搞混。

我把代码分成三层：输入层负责读题并归一化成统一表示，判定层只接收标准规则参数并返回结果，输出层负责按题目要求的格式输出。这样无论题目包装成“摆棋子”“分金币”还是“移动纸牌”，只要识别出底层模型，直接调用对应函数就行。

6. 做题最容易踩的坑：从规则细节到边界值

6.1 规则细节：取完最后一颗到底算赢还是算输

这个问题听起来简单，但实战中翻车率极高。巴什博弈、尼姆博弈、威佐夫博弈的经典结论都建立在“取最后一颗者胜”的前提下。一旦题目变成“取最后一颗者负”（称为反博弈），结论就要单独推导，不能直接套正版的判定。

以巴什博弈为例，正版是 n % (m + 1) == 0 先手必败；反版是 n % (m + 1) == 1 先手必败（部分资料还要求特殊处理 n <= m 的情况）。尼姆博弈的反版则更麻烦，当所有堆都只有 1 颗时，胜负取决于堆数的奇偶性；否则退化成常规判定。这些特例只有亲手推一遍才能记得牢，我建议你在笔记本上把正版和反版各推一遍，而不是靠死记硬背。

6.2 SG 值计算中的越界和记忆化问题

DFS 求 SG 值时，最容易犯的错是忘了初始化 sg 数组为 -1，导致递归过程中重复状态没有记忆化，指数级爆炸。另一个常见问题是递归深度：如果石子数量达到 10^5，且拿取方式也包括大数量，递归栈可能溢出。遇到这种情况，有两种处理思路：

• 改成自底向上的递推，从 sg[0] 开始依次算 sg[1]、sg[2]……直到 n，这种方式没有递归开销；
• 先在小范围内打印 SG 值，观察循环节，然后用模运算直接跳过中间过程。

我通常先用第二个思路判断题目有没有规律，如果没有规律再用第一个思路，因为自底向上写起来虽然安全，但代码长度和调试成本都会多一截。

6.3 威佐夫博弈的输入顺序与精度陷阱

威佐夫博弈的两个堆是无序的，有人习惯把它当成有序来处理，直接拿第一个数当成 a、第二个数当成 b，结果在 a > b 的场景下把差值算成负数。我自己的习惯是读入后立刻做 swap 保证 a <= b，后面再也不用管顺序问题。

精度陷阱前面提到过，这里再展开一句：如果你用的是 double 而不是 long double，在 k 非常大的时候，k * phi 的最低位可能会出现 1 的偏差，导致 tmp 比真实的 floor 值大 1 或小 1，最终判定错误。我见过不少选手因为这里丢分。如果题目数据范围超过 long long 能表示的范围，请放弃浮点，改用整数高精度方式处理。

6.4 输出策略：不止要判胜负，可能还要输出走法

部分题目不会只问“先手是否必胜”，而是要求你输出一种必胜策略，甚至要求按某字典序输出。这时候，巴什博弈还好办，因为策略固定；尼姆博弈需要遍历找到 target < a[i] 的那一堆；威佐夫博弈的必胜操作会比较绕，需要分三种情况讨论（从大堆拿、从小堆拿、两堆同时拿），每个情况还得判断操作后是否仍是局势合法。

应对这类题，我的经验是先落地一个函数：给定当前局面，返回所有可能让对手面对必败态的操作列表，然后再按题目要求的排序规则输出第一个。这样哪怕题目变化输出要求，你只需要改排序规则，不用重写判定逻辑。

6.5 常见问题速查表

这张表是我整理做题记录时总结出来的，基本覆盖了新手到进阶选手最容易卡住的点。每次写博弈题之前扫一眼，能省不少调试时间。

7. 取石子问题的扩展方向与深入研究

7.1 从取石子到图论游戏：有向图博弈的统一视角

取石子游戏看起来只是数学游戏，但它的背后是“有向图博弈”：把每一个局面看成图上的一个节点，把合法操作看成有向边，那么胜负判定就是在图上做拓扑式推导。这个视角最大的好处是能让 SG 函数顺理成章地推广到所有有限无偏博弈上，而不再局限于石子。

比如棋盘上的“移动棋子”游戏、纸牌游戏中“消去成对牌”的规则，本质上都能建模成有向图博弈。掌握了这个视角之后，你会发现自己遇到新题时有一种“降维打击”的感觉：不再需要针对每道题硬凑规律，而是先建图，再套 SG 框架。

7.2 取石子游戏变式：限制拿取集合、多堆交叉、随机性引入

取石子游戏的变式多到可以单独开一个专题。我挑几个常见的类型简单说一下：

• 限定拿取集合：每次只能取斐波那契数颗，或者只能取质数颗。这类问题 SG 值通常没有一眼看出的公式，需要打表找规律；
• 每次操作可以影响多堆：限制“最多选 k 堆，每堆取相同数量”，这就变成了“k 尼姆问题”，复杂度和普通尼姆完全不在一个量级；
• 引入随机因素：比如每次取的数量由骰子决定一部分，这时候博弈论和概率论就交汇了，判定从“必胜/必败”变成了“最大胜率策略”。

这些扩展方向在算法竞赛中不会一次全考，但理解它们的存在，能帮你判断一道题到底是该套模板，还是需要现场推新结论。

7.3 怎么继续深入：学习路径与练题建议

回到开头说的“算法笔记”这四个字，如果你想把博弈论这块彻底吃透，我的建议是分三步走：

第一步，把本文三个模型的正版和反版各写一遍代码，并手动推至少 10 组数据验证结论。这个步骤看起来枯燥，但能帮你把结论和推导过程牢牢绑定。

第二步，找一组低配题库，从巴什博弈、尼姆博弈、威佐夫博弈的模板题开始，然后尝试 SG 函数专项题，训练自己在 10 分钟内完成“建模——打表——找规律——套模板”的流程。我以前做题时会刻意把每一道题意想不到的地方记在文档里，一个月后回头看，会发现自己已经形成了一套“识别模型”的直觉。

第三步，尝试给取石子游戏换壳。把一个经典模型改造成故事背景不同但数学结构相同的题目，然后自己设计数据、验证结论。经常做这种训练后，你会发现所谓“新题”，大部分不过是旧模型换了个包装而已。

8. 一些不那么常说、但很实用的幕后心得

写到这里，我想分享几段很少在题解里看到、但对实际做题很有帮助的经验。

第一件事，是“异或和判定的直观理解”。很多初学者背下了尼姆博弈的异或结论，却不知道为什么异或能刻画石子堆之间的关系。我自己试着换过一个角度去理解：把每一堆石子的数量写成二进制，异或和不为 0 意味着这些二进制位中存在某些“位”没有配对成功。一次合法操作的本质，是选择一个堆，把它的二进制中的若干位翻转，而高位的支配性决定了必胜策略的存在。当你理解了这层含义，再遇到“每堆数量很大”的场景时，就不容易慌。

第二件事，是“比赛时应对没见过的博弈题”。如果真的遇到一道完全没有头绪的取石子题，我一般会先写一个暴力搜索程序，把所有小规模局面的胜负情况打出来。然后盯着表格，尝试把必败局面列出来，看它们之间有什么规律。很多时候，结论就是这样被“看”出来的，而不是被“推”出来的。这听上去不够优雅，但在限时比赛中，有效比优雅重要得多。

第三件事，是关于错题的管理。博弈论题目的代码量通常很小，所以你最大的风险不是写不出来，而是想错方向后debug会非常痛苦——因为代码太短，你甚至不知道该去哪里打日志。我的办法是：每次写出结论后，先自己构造几组“边界数据+随机小数据”，用暴力程序跑一遍对照结果，确认无误后再提交。不要嫌这一步麻烦，我靠它避免过太多次因为边界规则判断失误导致的罚时。

第四件事，是关于学习节奏。取石子游戏看起来是个小专题，但它牵涉到的思维能力——顺推归纳、异或位运算、无理数精度处理、状态压缩思想——都是算法学习的地基。我建议你不要把它当作一个孤立的板块来背，而是把它和动态规划、搜索剪枝、数学推导放在一起交叉练习。等你哪一天发现自己能在读题后 30 秒内判断出该用哪个模型，再回头做基础题，就会有一种“降维”的感觉。

第五件事，是代码风格。博弈题虽然短，但我依然会保持变量名可读、注释清晰的习惯。因为这类题经常在不同比赛里反复出现，你需要把“曾经的自己是怎么想的”留给“未来的自己”看。一行注释可能就能帮你省下重新推导半小时的时间，这笔账怎么算都不亏。