HDU 1846 这道题，在 OJ 圈子里的地位很特别：它是很多人接触博弈论的第一道题，也是“巴什博弈”最标准的入门模板。题目讲的是两个人轮流从一堆石子里取石子，每次至少取一个、最多取 m 个，谁取走最后一个谁赢，给定石子和上限，判断先手到底能不能赢。这类问题看起来像模拟题，数据一大就彻底没戏，但背后是一套非常漂亮的数学推理。这篇文章我会从题目理解、结论推导、代码实现、常见变形到刷题避坑，把巴什博弈一次讲透，适合刚接触博弈论、准备算法竞赛，或者只是单纯想把这道题弄明白的读者。
1. 拆开题目：这到底在让我们算什么
1.1 题目原文在说什么
题目名 Brave Game，剧情很简单：两个勇敢者玩游戏，桌上有 n 个石子，每轮每人可以取 1 到 m 个石子，取到最后一个石子的人获胜。输入第一行是测试数据组数 C，接下来每行两个整数 n 和 m，要求输出这一局先手能不能赢。
注意输出格式是英文小写，赢的一方输出first，输的一方输出second。这个细节看着小，实际影响很大，我见过不少人公式算对了，结果因为字符串大小写出问题，白丢一道题。
题目给了样例，两组数据：
2 23 2 4 3对应输出：
first second为什么会是这两个答案？23 和 2 组合起来，先手赢；4 和 3 组合起来，先手反而输。如果不看结论，直接靠直觉很难想清楚。实际上这两个样例恰好覆盖了巴什博弈的两种情况：n % (m + 1)不等于 0 时先手赢，等于 0 时后手赢。23 除以 3 余 2，先手赢；4 除以 4 余 0，后手赢。
1.2 为什么这道题值得单独写一篇
很多 OJ 上的博弈题一上来就是威佐夫博弈、尼姆博弈，要么是奇异局势，要么是异或运算，劝退效果拉满。而 HDU 1846 不一样，它把博弈论里最核心的一个思想——“必败态”和“必胜态”——藏在一个非常简单的问题里，只要你愿意多推导几步，就能把整个逻辑链串起来。
巴什博弈的结论本身只有一行：n % (m + 1) != 0则先手胜，否则后手胜。背下来只需要十秒钟，但我强烈建议不要只背这个式子。因为后续很多博弈题，考察的核心并不是“你知不知道结论”，而是“你能不能从局面递推中找到周期”。巴什博弈就是找到周期的最朴素例子，它帮你建立起的递推思维，可以直接迁移到尼姆博弈、SG 函数、甚至一些奇怪的图游戏上面。
加上题目的 n 和 m 范围通常给得非常大，靠 BFS、DFS、记忆化搜索去模拟整局游戏，要么超时要么爆栈。这种“数据范围暗示数学做法”的套路，也是竞赛题里很常见的信号。
2. 巴什博弈完整推导：从“玩一下”到“数学归纳”
2.1 先别背公式，亲手玩几个小局面
为了不空谈理论，我们先固定一个简单的参数：每次最多取 3 个石子，也就是 m = 3。然后从 n = 1 开始，一个一个看先手会输还是会赢。
| 石子数 n | 先手策略分析 | 结果 |
|---|---|---|
| 1 | 一次取完，获胜 | 先手赢 |
| 2 | 一次取 2 个，获胜 | 先手赢 |
| 3 | 一次取 3 个，获胜 | 先手赢 |
| 4 | 取 1 留 3，后手全取；取 2 留 2，后手全取；取 3 留 1，后手全取 | 先手输 |
| 5 | 先取 1，把 4 个石子留给后手，后手面对 n=4 必输 | 先手赢 |
| 6 | 先取 2，把 4 个石子留给后手 | 先手赢 |
| 7 | 先取 3，把 4 个石子留给后手 | 先手赢 |
| 8 | 无论取 1、2 还是 3，剩下的数量都是 5、6、7，这些局面轮到后手时后手都能赢 | 先手输 |
观察这张表，能发现一个明显规律：n = 4 和 n = 8 是先手输，其他列举出来的数先手赢。每 4 个数会出现一个“先手必败”的情况，而 4 刚好等于 m + 1。这不是巧合，而是整个巴什博弈的核心结构。
如果你不想列表格，也可以把局面按“轮到谁取”来标记：还剩 0 个石子时，当前玩家已经输了，所以 0 是必败态；还剩 1 到 m 个时，当前玩家可以一次取完，所以是必胜态；还剩 m + 1 个时，不管当前玩家怎么取，都会留给对手一个 1 到 m 的局面，对手一次取完，所以当前玩家必败。这就像多米诺骨牌，从终局一路往回推。
2.2 关键技巧：把每轮看成一个固定套餐
前面那个表格能看出规律，但还不能解释“为什么是 m + 1”。这里有一个特别直观的理解方式：后手玩家拥有一种“跟牌权”。
假设先手某一轮取了 k 个石子，k 的范围是 1 到 m，那么后手可以取m + 1 - k个石子。两个人一轮合起来，一共取走了k + (m + 1 - k) = m + 1个石子。也就是说，后手可以把自己的取法绑定在先手的取法上，保证每一轮都从总堆里稳定地消耗掉 m + 1 个石子。
如果总石子数 n 恰好是 m + 1 的倍数，后手只要一直使用这个“补足 m + 1”的策略，石子数就会一轮一轮地减少 m + 1，最后必然轮到先手面对一个 1 到 m 的局面，先手取完，然后游戏结束？这里要小心，实际应该是后手补上最后一轮的石子，由后手取走最后一个。比如 n = 4，m = 3，先手取 1，后手取 3 就拿走了最后一个，后手赢；先手取 3，后手取 1 也能拿走最后一个，还是后手赢。
反过来，如果 n 除以 m + 1 有余数 r，也就是n % (m + 1) = r，其中 r 在 1 到 m 之间。先手第一轮就取 r 个，直接把石子数变成 m + 1 的倍数，把这个“后手必胜套餐”原封不动地塞给对手。之后先手转换角色，把自己当成上面的“后手”，每轮都取m + 1 - 对手取的数量，最终由先手取走最后一个。
2.3 严格一点的数学证明
如果你希望在题解里写出让人信服的推导，或者想在面试/教学时讲清楚，可以这样归纳：
定义局面 n 为必败态：轮到当前玩家取石子，无论他怎么取，最终都会输；定义必胜态：至少存在一种取法能让当前玩家最终获胜。
目标局面是 0 个石子，此时没有石子可取，而取走最后一个石子的人已经赢了，所以轮到的人必败。也就是说 0 是必败态。
当n % (m + 1) == 0时，假设当前玩家取 k 个，剩余石子为n - k，这个数对 m + 1 取模的结果是(m + 1 - k) % (m + 1)。因为 k 在 1 到 m 之间，所以m + 1 - k在 1 到 m 之间，不等于 0。换句话说，当前玩家无论怎么取，都会把局面送到一个“非 m + 1 倍数”的状态，也就是必胜态。既然所有能走到的下一步都是必胜态，当前局面就是必败态。
当n % (m + 1) != 0时，令余数为 r。当前玩家只要取 r 个石子，剩余石子数n - r就是 m + 1 的倍数，这是一个必败态。能够一步走到必败态的局面，就是必胜态。
两边都证明完毕，结论成立。
2.4 用报数游戏理解这套逻辑
巴什博弈在现实里最经典的例子是报数游戏：两个人轮流报数，每次可以报 1 到 3 个数，谁报到 30 谁赢。这本质就是 n = 30、m = 3 的巴什博弈。
按公式算一下，30 % 4 = 2，所以先手应该先报 2 个数，把数字报到 2。之后不管对手报 1 个、2 个还是 3 个数，先手都补足 4 个数。对手报 1 个数，先手就报 3 个；对手报 2 个，先手就报 2 个；对手报 3 个，先手就报 1 个。每一轮下来，双方合计推进 4 个数，最后先手一定能报到 30。
这个例子特别适合拿来给朋友演示，不需要纸和笔，直接在手机上随便玩玩就能验证。你只要记住了“先报余数，之后补 m + 1”的口诀，哪怕不写代码，也能在饭桌上当个小游戏赢一晚上。
3. 代码实现与提交细节：从思路到 AC
3.1 C/C++ 版本：几行代码就能过
C++ 写法非常简短，核心判断就是一行取模。
#include <cstdio> int main() { int c; scanf("%d", &c); while (c--) { int n, m; scanf("%d%d", &n, &m); if (n % (m + 1) != 0) { printf("first\n"); } else { printf("second\n"); } } return 0; }时间复杂度是 O(C)，每组数据只做一次取模和一次比较，空间复杂度 O(1)。哪怕 C 有十万组、n 有 2 的 31 次方那么大，这段代码也是瞬间出结果。这也是数学结论题和模拟题最大的区别，你不必真的把游戏过程走一遍。
用scanf和printf是竞赛里的习惯，能避免 iostream 在某些老评测机上因为同步问题带来的性能损耗。如果你用cin、cout，也建议加上ios::sync_with_stdio(false)取消同步。
3.2 Java 版本：注意输入输出的细节
Java 写起来同样直接，但输入输出部分如果偷懒可能超时，建议用BufferedReader而不是Scanner处理大规模数据。
import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int c = Integer.parseInt(br.readLine().trim()); StringBuilder sb = new StringBuilder(); while (c-- > 0) { String[] parts = br.readLine().split(" "); int n = Integer.parseInt(parts[0]); int m = Integer.parseInt(parts[1]); if (n % (m + 1) != 0) { sb.append("first\n"); } else { sb.append("second\n"); } } System.out.print(sb); } }这里用StringBuilder把结果攒起来再一次输出，能明显减少 IO 次数。如果每组都System.out.println一次，在数据量大时会有可感知的额外耗时。Java 在算法竞赛里本来就容易吃性能的亏，能省的地方都要省。
3.3 提交前必须检查的细节
第一，判断条件别写反。n % (m + 1) == 0的时候输出second，不等于 0 的时候输出first。我最早做这题时一度以为余数为 0 是先手稳了，实际上完全反了。建议自己在草稿纸上写一个 n = 4、m = 3 的例子，确认一遍再提交。
第二，注意 m + 1 会不会溢出 int。虽然多数题目的范围很温和，但如果 n 和 m 给到接近 2^31，m + 1 依然不会溢出 int（因为 m 最大也就 2^31 - 1 左右），不过用 long 更稳妥，Java 里直接用 long 也完全没问题。
第三，多组输入的时候，读完 C 之后每一行都要读完整。个别题目可能在某组数据前面有额外的空格或空行，用split解析时要做好防御，避免数组越界或 NumberFormatException。
第四，输出大小写严格按要求来。这题要求小写first、second，但有些类似的题目要求首字母大写，提交前一定要重新看一下原题描述，不要凭记忆套用。
4. 巴什博弈的变体与延伸：一道题变成一类题
4.1 反巴什博弈：取走最后一个的人反而输
巴什博弈最常见的变体是“拿到最后一个石子的人判负”，也就是 Misère Bash Game。规则改动只有一处，结论却完全不同。
先直接给结论：当n % (m + 1) == 1时，先手必败；否则先手必胜。
这个结论看起来和正巴什很像，只把“余 0”换成了“余 1”，但推导逻辑值得重新捋一遍。在正巴什里，0 个石子是必败态，因为轮到的人已经输了；但在反巴什里，0 个石子的意思是上一个玩家取走了最后一个并且判负，当前玩家什么都没做就赢了，所以 0 是必胜态。再看 1 个石子，当前玩家只能取走这 1 个，然后判负，所以 1 是必败态。
从 1 开始往回推，2 到 m + 1 个石子时，当前玩家可以取到只剩 1 个，把必败态扔给对手，所以必胜；m + 2 个石子时，取 1 个剩 m + 1（必胜态），取 2 个剩 m（必胜态）……取 m 个剩 2（必胜态），所有下一步都是必胜态，所以 m + 2 是必败态。这个排列会以 m + 1 为周期循环，必败态正好是石子数对 m + 1 取模等于 1 的局面。
如果比赛遇到这道变体，别想当然地套正巴什的代码，直接把判断条件从n % (m + 1) != 0改成n % (m + 1) != 1就行，但理解周期来源更重要。
4.2 从一堆石子到多堆石子：尼姆博弈和威佐夫博弈
巴什博弈研究的是一堆石子，限制每次取的数量范围。如果放宽规则，变成“有若干堆石子，每次可以选一堆取任意数量”，这就是经典尼姆博弈。尼姆博弈的结论是：把所有堆的石子数做按位异或，结果非 0 则先手赢，结果为 0 则后手赢。它和巴什博弈一样，都是基于必败态的递推，只是必败态的判定从“整除”变成了“异或和为 0”。
如果只有两堆石子，每次可以取一堆中的任意数量，或者同时从两堆中取相同数量，这就是威佐夫博弈。它的必败态是一组奇异局势，和黄金分割比有关。初次接触时可能觉得结论很玄，但它的思考路径和巴什博弈一模一样：从小局面倒推，标出必败态，找通项。
我建议按“巴什博弈 → 尼姆博弈 → 威佐夫博弈 → SG 函数”的顺序刷题。巴什博弈是地基，尼姆博弈让你理解位运算和状态表示，威佐夫博弈打开数学分析的视角，SG 函数则把所有有限无偏博弈统一成一个框架。
4.3 SG 函数视角：原来巴什博弈就是它
如果你已经接触过 SG 函数，会发现巴什博弈的结论非常自然地嵌入其中。对一个局面 x，SG 值定义为所有后继局面 SG 值的 mex（最小非负未出现值）。在巴什博弈里，局面 x 的后继局面是 x - 1 到 x - m，所以 SG(x) = x % (m + 1)。
当 SG 值为 0 时，这个局面是必败态，对应后手胜；SG 值非 0 时是必胜态。换句话说，前面花大力气推导的巴什博弈，就是 SG 函数最简单的一个特例。先掌握巴什，再学 SG，你会觉得那个抽象的 mex 定义突然有了落地感。
5. 练习建议与常见误区整理
5.1 我在实战中踩过的坑
第一坑：用模拟做。n 和 m 给到十亿级别时，我以为可以靠循环按轮次减石子，结果样例过了，交上去超时。后来才反应过来，博弈论题目如果考察目的明确，往往是让你找数学规律，不是让你复现游戏过程。判断一件事该不该模拟，先看数据范围，只要数据大到一个循环都危险，就该停下来想结论。
第二坑：DP 表打错方向。我有一段时间特别迷信动态规划，不管什么题都想开数组递推。巴什博弈确实可以用 DP 从 0 推到 n，状态转移也只有 m 种，但问题是 n 太大时数组根本开不下。这就是为什么结论推导比 DP 打表重要，你不是不会 DP，而是 DP 解决不了规模问题。
第三坑：背了公式但没验证样例。公式背得出，代码写得也对，但输出第一组23 2时我竟然想当然地认为余数是 2 应该后手赢，交上去 WA 了。这一类错误非常隐蔽，因为它不是代码层面的 bug，而是思路层面的 bug。写完之后把题目样例手算一遍，既是对公式的检验，也是对题意的再确认。
第四坑：多组数据循环里忘记读下一行。用某些语言的输入流时，如果上一组没读完或者多读了空白，会影响后续数据解析。解决办法是每组读完就立刻调一次读取操作，保证输入流位置正确。
第五坑：把题目里的输出提示看漏。有些题目输出要求大写First、Second，有些还带冒号和空格。这种非算法因素最容易丢分，而且一旦错就是整题错，连部分分都没有。交之前花十秒钟看 Output 部分，再花十秒钟对样例格式，值得。
5.2 快速判断一道博弈题到底考什么
刷题多了，我总结了一个简单的辨别方法，可以帮你快速定位题目类型。
| 题目特征 | 大概率考点 |
|---|---|
| 单堆石子，每次取 1 到 m 个，取最后一个赢 | 巴什博弈 |
| 单堆石子，每次取 1 到 m 个，取最后一个输 | 反巴什博弈 |
| 多堆石子，每次取一堆任意数量 | 尼姆博弈 |
| 两堆石子，可取一堆任意或两堆相同数量 | 威佐夫博弈 |
| 石子分成多堆，取法有额外限制 | SG 函数 / 找规律 |
| 走棋子、翻硬币、排列等图游戏 | SG 函数 / 状态压缩 |
这个表不是万能定律，但足够应付绝大多数入门题。最关键的一个技巧是：遇到不熟悉的博弈题，先在小数据范围内打表，观察必败态的分布，再找规律。巴什博弈的必败态周期是 m + 1，这个周期就是靠小局面观察出来的。很多看似复杂的题目，最后都能通过“打表找周期”这个组合拳解决。
我个人在实际做题里还有一个习惯：每次写完结论题，都顺手写一个暴力验证程序，对拍小数据。比如这题，我写一个递归函数判断某个局面是必胜还是必败，再和取模公式的结果对比 1 到 100 的所有 n、m 组合。这种对拍每次只花几十秒，但能让我对结论的信心提升一大截。以后再遇到类似的巴什变体，哪怕公式忘了一半，也能靠暴力推出来。
如果这篇文章对你有一点点帮助，最值得带走的一句话是：巴什博弈的精髓不是n % (m + 1)这个式子，而是“必败态会周期性出现，先手要做的就是第一步把局面交给对手的必败态”。后面无论是尼姆、威佐夫还是 SG 函数，回头看都是在做同一件事：找到必败态，然后把对手送进去。
