企业官网建设流程全解析

想当年我第一次在OJ上看到取石子问题，第一反应是“这也能算难题？”——状态一个数组存过去，要么DFS要么DP，写出来再说。结果数据范围一出来，直接懵了：(n) 给到 (10^{18})，根本不是让你用搜索硬怼的。再后来陆陆续续刷了巴什博弈、Nim博弈、威佐夫博弈、斐波那契博弈，才发现这套东西真正的名字叫“组合博弈论”，而取石子游戏就是理解这门学问最顺手的入口。最近算法群和热榜上“博弈论”这个词又频繁出现，很多人在问到底怎么入门、怎么下手判断胜负，我觉得与其零散刷题，不如把经典的取石子模型一次性串起来，把必胜态、必败态、异或和、SG函数这些概念放到同一个框架里讲清楚。

这篇文章面向两类人：一是刚接触博弈论、手里有几道取石子题但只会套模板的入门选手；二是已经会做普通Nim、但遇到威佐夫、反Nim、斐波那契博弈会卡壳的进阶选手。我会从一个最朴素的问题“谁站在原地谁输”开始，一路推到SG定理，顺便把我在实际刷题和比赛中踩过的坑也一并交代清楚。

1. 破题：必败态与必胜态，先搞懂“游戏状态”能怎么迁移

1.1 两个词就能概括全部博弈：N态和P态

很多讲博弈的文章直接丢结论，比如“异或和为零就是必败”，却不解释为什么。这是最劝退的讲法。先把基本概念定下来。

对一个公平组合游戏，任意一个局面可以分成两类：

• 必胜态（N态）：当前行动的人有策略保证自己最终获胜。
• 必败态（P态）：当前行动的人无论如何操作，对方都有策略使自己最终获胜。

这里有两个最底层的转移规则：

1. 如果某个状态存在一条边能走到P态，那么这个状态是N态。
2. 如果某个状态所有边都只能走到N态，那么这个状态是P态。

换句话说，站在必败态的选手只能眼睁睁把胜势送给对手，而站在必胜态的选手只需要找到一个能把对手推进P态的操作。这个定义是递归的，终点也很简单：在“取完最后石子的人获胜”规则下，没有石子可取的状态就是P态，因为轮到谁谁就输了。

1.2 巴什博弈：(m+1) 这个周期是怎么冒出来的

巴什博弈是最简单的取石子模型：有一堆石子，总数 (n)，每次至少取 (1) 颗，最多取 (m) 颗，取到最后石子的人获胜。

我刚开始也和人一样记结论：(n \bmod (m+1) = 0) 时先手必败，否则先手必胜。但我花了好久才真正理解为什么偏偏是 (m+1)。

道理其实很直观。假设当前轮到对方行动，他取 (x) 颗（(1 \le x \le m)），我总能取 (m+1-x) 颗补回去。这样一轮下来，两个人合计取走的石子数是固定的 (m+1)。所以只要我能把局面控制成“剩余石子数是 (m+1) 的倍数”，并且让对手先面对这个局面，那么无论他怎么取，我都能把余数重新补回 (m+1) 的倍数。重复下去，最后一组 (m+1) 颗一定是对手先取，他取不完也取不没，我补上最后一手，结束游戏。

所以判断就一句话：

• (n \bmod (m+1) == 0)：先手必败。
• 否则：先手第一步取 (n \bmod (m+1)) 颗，之后把双方每轮总取数保持在 (m+1)，先手必胜。

代码更是短到让人怀疑：

bool bashGame(long long n, long long m) { return n % (m + 1) != 0; }

把这个模型稍微变一变，比如“每次只能取 ({1,3,4}) 颗”，就不能再用模数套了。这个时候老老实实用一个数组推状态即可：(f[0]=0)，对每个 (i) 扫描所有允许的步长 (s)，如果 (i-s \ge 0) 且 (f[i-s]=0)，那么 (f[i]=1)。这种“由P态反推N态”的打表方式，是后面一切复杂问题的根基。

2. 普通Nim的“异或邪术”：为什么几堆石子变成了XOR

2.1 核心定理：异或和决定一切

普通Nim博弈规则如下：有若干堆石子，双方轮流从任意一堆中取走至少一颗石子（可以整堆取完），取到最后一颗石子的人获胜。

这个游戏的结论大家应该都听过：把所有堆的石子数做异或，记作 (X = a_1 \oplus a_2 \oplus \cdots \oplus a_n)，如果 (X = 0)，先手必败；否则先手必胜。

我第一次看到这个结论时很抗拒——异或是位运算，石子数是整数，这两个是怎么扯上关系的？后来看了一个证明才通透。

证明分两步：

1. 从 (X \ne 0) 出发，一定能找到某一堆 (a_i)，把它变成 (a_i' = a_i \oplus X)，并且满足 (a_i' < a_i)。因为 (X) 的最高位为 (1)，必然至少有一堆在这一位也是 (1)，改变这一位后 (a_i) 的高位减小，所以 (a_i') 确实比 (a_i) 小。这样一次操作后，新的异或和为： [ a_1 \oplus \cdots \oplus a_i' \oplus \cdots \oplus a_n = X \oplus X = 0 ] 也就是说，任何非零局面都能一步走到零局面。

2. 从 (X = 0) 出发，你取走某一堆若干颗后，这堆从 (a_i) 变成 (a_i'')，且 (a_i'' \ne a_i)。此时新的异或和变成 (a_i \oplus a_i'')，这个值不可能为 (0)，因为两个不同的数异或不可能是零。也就是说，零局面只能走到非零局面。

这两条合在一起，正好对应前面说的P/N态转移规则：(X=0) 是P态，(X\ne0) 是N态。

2.2 一个实际走位，看懂先手怎么赢

举个例子，三堆石子分别是 ((1,3,4))。先算 (1 \oplus 3 \oplus 4 = 6)，非零，所以先手必胜。那么具体怎么走？

(X=6) 的二进制是 (110)，最高位是第 (2) 位（从0开始数），需要找一堆在这一位上也包含 (1) 的。(1) 的二进制是 (001)，没有；(3) 的二进制 (011)，第 (2) 位是 (0)；(4) 的二进制 (100)，符合条件。于是把这一堆变成： [ 4' = 4 \oplus 6 = 2 ] 也就是从4颗那堆里取走2颗，剩2颗。此时局面变为 ((1,3,2))，计算 (1 \oplus 3 \oplus 2 = 0)，正好把对手推入P态。

之后无论对手怎么取，你都能用同样的方式把局面拉回零异或状态。这就是Nim博弈中“保持异或和为零”的操作策略。

2.3 nim博弈的两个易错点

第一，异或运算的优先级很低，我自己写代码时踩过坑：

if (x ^ y == 0) // 错！== 优先级高于 ^

正确的是：

if ((x ^ y) == 0)

第二，Nim博弈的“取到最后一颗石子获胜”这个前提很关键。如果题目把规则改成“取到最后一颗石子的人判负”，也就是反Nim，结论会完全不一样，这个我放到第四节专门说。

3. 变体实战：威佐夫、斐波那契、反Nim三种高频题型

3.1 威佐夫博弈：两堆石子里的黄金比例

威佐夫博弈长这样：有两堆石子，两个人轮流操作，可以在一堆中取任意多颗，也可以在两堆中同时取走相同数量的石子，取最后一颗者胜。

这个模型不能直接用XOR，因为规则允许“同时动两堆”，整个局面并不是相互独立的若干互不相干的子游戏。但可以打表把必败局面找出来。

记两堆数量为 ((a,b))，假设 (a \le b)。从头枚举：

• ((0,0)) 是必败态。
• ((1,2)) 是必败态。
• 下一个必败态是 ((3,5))。
• 再下一个是 ((4,7))。

这些必败态也叫“奇异局势”。规律是：每次取没有在之前出现过的最小整数作为新局势的 (a_k)，然后 (b_k = a_k + k)，其中 (k) 从0开始编号。于是得到序列：

看到 (b_k - a_k = k)，而 (a_k = \lfloor k \cdot \varphi \rfloor)，其中 (\varphi = \frac{1+\sqrt5}{2})，这就是黄金比例。这个结论来自Beatty定理，竞赛里一般不需要证明，直接用即可。

所以判断方法就一句话：设两堆为 (a \le b)，令 (k = b - a)，如果 [ a = \left\lfloor k \cdot \frac{1+\sqrt5}{2} \right\rfloor ] 那么当前是必败态，先手输；否则先手胜。

代码实现要注意浮点精度问题：

bool wythoff(long long a, long long b) { if (a > b) swap(a, b); long long k = b - a; long double phi = (1 + sqrtl(5.0L)) / 2.0L; long long tmp = (long long)(k * phi + 1e-9L); return a == tmp; // true 表示必败 }

这里我习惯加一个极小的欧拉值 (10^{-9})，是为了防止浮点误差导致整型向下取整时差1。后面第五节再展开讲这个坑。

3.2 斐波那契博弈：对手你最多只能翻倍

斐波那契博弈的规则比较别扭：有一堆石子，第一个人可以取任意数量但不能全部取完；此后每个人取的颗数不能超过对手上一次取的颗数的两倍。取到最后一颗的人获胜。

结论同样漂亮：当且仅当石子总数 (n) 是斐波那契数时，先手必败。

第一次接触这个结论时，我完全无法理解“劣势方到底输在哪儿”。后来看了一个从Zeckendorf定理入手的解释，才算真正搞明白。

Zeckendorf定理说：任何一个正整数都可以唯一表示成若干个不相邻的斐波那契数之和。比如 (n=14) 时： [ 14 = 13 + 1 ] （因为13和1在斐波那契序列里不相邻）。

如果 (n) 本身是斐波那契数，比如 (n=13)，先手无论第一步取多少颗，最多只能取12颗。后手有个巧妙的应对策略：把剩下的石子按照Zeckendorf定理拆成若干“块”，用取石子把大块化小、把小块补满，总能在回合内“控制”局面节奏。这个过程比较抽象，竞赛中记住结论+打表验证就够用。

如果 (n) 不是斐波那契数，先手必胜，而且第一步取法是：取出最接近 (n) 且小于 (n) 的斐波那契数，取走 (n) 减去这个数的差值。之后把局面当作“对手面对一个斐波那契数的堆”来处理。

写个判断函数：

bool fibGame(long long n) { long long a = 1, b = 1; while (b < n) { long long c = a + b; a = b; b = c; } return b == n; // true 表示先手必败 }

这个模型最典型的应用是在阶梯博弈类的入门题里，很多题目只是换了个包装，核心还是“判断n是否是斐波那契数”。

3.3 反Nim游戏：最后取到石子的人输，结论完全反转

反Nim博弈和普通Nim唯一的区别是判负条件互换：取到最后一颗石子的人判负。

这个条件导致XOR结论失效。我第一次做这类题，直接拿普通Nim的异或判了一发，结果WA到怀疑人生。

反Nim的判断分两种情况：

1. 如果所有堆的石子数都为 (1)：这时胜负只取决于堆数的奇偶性。堆数是奇数，先手必须取走一堆 (1)，剩偶数个 (1) 给对方，对方拿完最后一堆时自己也拿完了，但根据规则是“取最后一颗者负”，所以先手输。奇数个1 → 必败。
2. 如果存在某堆石子数大于 (1)：那么结论和普通Nim正好相反——异或和为零时先手必胜，异或和不为零时先手必败。

这个反直觉的结论第一次见时很容易记混。我后来给自己编了个口诀：普通Nim看异或，反Nim先看全一，全一奇偶定胜负，非全一则异或反着判。

判断代码：

bool antiNim(vector<long long>& piles) { bool allOne = true; long long xr = 0; for (long long x : piles) { xr ^= x; if (x > 1) allOne = false; } if (allOne) { return piles.size() % 2 == 0; // 偶数个1，先手胜 } else { return xr != 0; // 这里和普通Nim恰好相反 } }

注意，这段代码返回的是“先手是否必胜”。

4. 更大杀器：Sprague-Grundy函数，把“规则随你定”变成异或

4.1 SG函数和mex运算

Nim博弈里各堆是相互独立的，所以可以直接异或。但巴什博弈的步长集合是 ({1,m})，威佐夫博弈允许同时动两堆，斐波那契博弈限制上一轮操作，这些规则各自不同，难道每一种都要重新找规律？

不需要。Sprague-Grundy定理统一了它们。

先定义SG函数。对一个状态 (s)，它所有一步可达的后继状态记为 (T(s))。定义： [ SG(s) = \operatorname{mex}{SG(t) \mid t \in T(s)} ] 其中 (\operatorname{mex}) 表示“集合中未出现的最小非负整数”。终点状态没有后继，其SG就是0。

然后神奇的事情发生了：如果状态 (s) 代表一个“独立可叠加”的子博弈，那么整个组合博弈的胜负只取决于所有子博弈SG值的异或和。异或和为零就是必败态，否则是必胜态。

为什么SG定理能把任何游戏转化成Nim？你可以把SG值理解为“这个状态相当于一个拥有SG(s)颗石子的虚拟Nim堆”。一堆SG为 (x) 的子游戏，能走到SG为 (0,1,\ldots,x-1) 的所有时代替Nim堆中“取任意颗石子”的效果；至于更大的SG值，组合游戏由多个子堆组成时，反正最后都是看异或。这个视角一旦建立，做题就变成机械计算。

4.2 手动推一个SG表

以最基础的取石子为例：有一堆石子，每次只能取 ({1,3,4}) 颗，取最后一颗者胜。求SG函数。

• (SG(0)=0)
• (SG(1)=\operatorname{mex}{SG(0)}=\operatorname{mex}{0}=1)
• (SG(2)=\operatorname{mex}{SG(1)}=\operatorname{mex}{1}=0)
• (SG(3)=\operatorname{mex}{SG(2), SG(0)}=\operatorname{mex}{0,0}=1)
• (SG(4)=\operatorname{mex}{SG(3), SG(1), SG(0)}=\operatorname{mex}{1,1,0}=2)
• (SG(5)=\operatorname{mex}{SG(4), SG(2), SG(1)}=\operatorname{mex}{2,0,1}=3)
• (SG(6)=\operatorname{mex}{SG(5), SG(3), SG(2)}=\operatorname{mex}{3,1,0}=2)

可以发现SG值会从某个位置开始循环，这就是所谓的“周期规律”。竞赛中一般不用在题目里找周期，直接把SG打表打到上限即可。

4.3 代码模板：时间戳优化

如果每次求mex都开一个bool vis[]然后memset清空，状态一多就会超时。常见的优化是引入时间戳：

const int MAXN = 100005; int sg[MAXN], vis[MAXN], stamp; void calcSG(int n, vector<int>& steps) { sg[0] = 0; for (int i = 1; i <= n; i++) { ++stamp; for (int s : steps) { if (i - s >= 0) { vis[sg[i - s]] = stamp; } } sg[i] = 0; while (vis[sg[i]] == stamp) sg[i]++; } }

这样每次只修改vis中碰到的位置，不用全局清零，复杂度大致是 (O(n \cdot |steps|))。

对于多个堆，直接异或所有SG值：

int ans = 0; for (int i = 0; i < m; i++) ans ^= sg[a[i]]; if (ans == 0) printf("先手必败\n"); else printf("先手必胜\n");

这里再次出现异或，是不是瞬间觉得普通Nim其实只是SG定理的一个特例？确实如此，Nim游戏每个堆的SG值就是石子数本身。

5. 实战中踩过的坑，以及怎么快速判断该用哪个模型

5.1 模型识别：看到题目不要直接无脑SG

取石子的变体一眼看不完，但根据状态特征可以快速缩小范围。我一般先回答三个问题：

1. 这是几堆石子？
2. 每次取石子的限制是什么？
3. 判负条件是“取到最后者胜”还是“取到最后者负”？

回答完基本能对号入座，整理成一张表：

这张表基本上覆盖了绝大多数算法竞赛里出现的取石子裸题。如果题目不满足上面任何一种，再考虑SG函数。

5.2 浮点精度：威佐夫判断不要裸用double

威佐夫博弈里有一个 (\lfloor k \cdot \varphi \rfloor) 的计算。(k) 可能很大，如果直接用double算，精度不够时向下取整会出偏差。我实测过，(k) 到 (10^9) 左右，double已经不够安全。我踩过这个坑之后，改用long double，并加一个极小的修正量：

long double phi = (1 + sqrtl(5.0L)) / 2.0L; long long tmp = (long long)(k * phi + 1e-9L);

如果题目给出的数据范围到了 (10^{18}) 级别，单纯靠浮点计算的人会吃大亏。更稳妥的做法是改用高精度整数模拟，或者提前预处理所有奇异局势，用二分判断。不过在一般校赛和面试中，long double + 1e-9已经够用。

5.3 数据范围决定算法，不决定模型

取石子问题经常把 (n) 给到 (10^{18})，这是在逼你放弃O(n)的DP，回到数学规律的判断上。很多人一看到“石子堆”就直接开sg数组，结果内存爆掉，还浑然不觉。

我的建议是：先看一眼数据范围，再决定方案。

• (n \le 10^6)：可以放心打表做SG。
• (n \le 10^{18})：必是公式题或周期题，优先考虑巴什、Nim、威佐夫、斐波那契。
• 多个堆但每堆状态数很小：先分别算SG，再异或。

5.4 反Nim的“全一堆”特判是最容易丢分的地方

反Nim里，如果所有堆都是1，异或和不为零，但先手反而必败。这个边界条件极其阴险。我见过很多代码，主逻辑写得头头是道，却漏了这个特判，导致奇偶性反了。

写题时还容易把普通Nim和反Nim的代码混用。建议把两种判断封装成两个函数，命名明确区分，免得复核时看花眼。

5.5 递归记忆化搜索时小心爆栈

SG除了递推，也可以用记忆化DFS写。但递归深度在某些“取很少颗石子”的题目中可能很深。比如步长集合里有 (1)，每层只减1，5000层就爆栈。所以能用递推就尽量用递推，尤其是OJ环境栈空间不大时。

6. 一些竞赛之外的体会：为什么取石子游戏值得认真玩

最后说点题外话。取石子游戏看起来只是“数学题里的一个文件夹”，但它锻炼的能力非常底层：识别状态、建立转移、找不变量、从局部最优推导全局结论。这套思维和动态规划相似，但比DP多了一层“博弈双方都在理性行动”的假设，写代码时一般不需要显式模拟对手，因为P/N态和SG定理已经把对手的最优策略压缩进了状态判断里。

我给初学者的建议是：不要只背结论，一定要自己推一遍巴什博弈的 (m+1) 周期，以及威佐夫博弈的奇异局势表。把前面的表打到第20行，盯着它看一会儿，你会发现“下一个必败态最小未出现整数 + 等差数列”的模式会自己浮现出来——这种从原始数据里看出规律的快感，比死记公式强多了。

如果以后遇到一个全新的取石子变体，我一般直接打表观察SG序列，找周期，再尝试证明。很多所谓的高难题，最终都逃不过“SG异或”这个框架。把本文的模型吃透，你已经能搞定绝大部分相关考点了。