核心逻辑与数学原理
Nim 游戏是组合博弈论中最经典的基石模型。理解 Nim 游戏的核心在于掌握 Nim-Sum（尼姆和） 及其背后的状态空间映射。
1. 经典 Nim 游戏规则
有 $n$ 堆石子，每堆石子的数量分别为 $a_1, a_2, \dots, a_n$。两名玩家轮流行动，每次操作可以选择任意一堆石子，并从中拿走任意正整数个石子（甚至可以把整堆拿光）。最后无法进行合法移动（即所有石子堆数量均为 0）的玩家判定为输。
2. Bouton 定理：Nim-Sum 判定的数学本质
对于一个特定的 Nim 游戏状态 $(a_1, a_2, \dots, a_n)$，定义其 Nim-Sum 为所有石子堆数量的按位异或（XOR）和，记作 $S$：
$$S = a_1 \oplus a_2 \oplus \dots \oplus a_n$$
Bouton 定理指出：
- 若 $S = 0$，则当前状态为 P-position（必败态）。
- 若 $S \neq 0$，则当前状态为 N-position（必胜态）。
定理的底层数学证明（基于 P/N 三大公理）
- 终结状态验证：当游戏结束时，所有 $a_i = 0$，此时 $S = 0 \oplus 0 \dots \oplus 0 = 0$。满足终结状态为 P 状态的公理。
- $S \neq 0$ 必然可以转移到 $S = 0$： 假设当前 $S = k \neq 0$。设 $k$ 的二进制最高位是第 $d$ 位。在所有石子堆中，必然存在至少一堆石子 $a_i$，其二进制的第 $d$ 位也是 $1$（否则异或和的第 $d$ 位不可能是 $1$）。 此时我们有：
$$a_i \oplus k < a_i$$
（因为异或 $k$ 会把 $a_i$ 的第 $d$ 位由 $1$ 变为 $0$，而比 $d$ 更高的位保持不变）。 因此，玩家完全可以从第 $i$ 堆石子中拿走一部分，使其数量精确减少到 $a_i' = a_i \oplus k$。 此时，新的异或和变为：
$$S' = S \oplus a_i \oplus a_i' = k \oplus a_i \oplus (a_i \oplus k) = 0$$
满足“可达 P 必为 N”的公理。 3. $S = 0$ 无论怎么走都会转换为 $S \neq 0$： 若当前 $S = 0$，玩家选择改变其中的某一堆 $a_i$ 变成 $a_i'$（由于规则限制，$a_i' \neq a_i$）。 新的异或和为：
$$S' = S \oplus a_i \oplus a_i' = 0 \oplus a_i \oplus a_i' = a_i \oplus a_i'$$
因为 $a_i' \neq a_i$，所以 $a_i \oplus a_i' \neq 0$，即 $S' \neq 0$。 满足“后继皆 N 必为 P”的公理。
算法推导与状态设计
由于 Bouton 定理将原本复杂的博弈树直接坍缩为简单的二进制异或运算，这使得状态维护的复杂度从指数级骤降为 $O(N)$。
先手必胜第一步的决策生成
在实际竞赛中，题目不仅会要求判断先手胜负，还经常要求输出先手第一步有多少种完美的必胜走法，或者具体的策略方案。
根据证明第 2 条，只要满足 $(a_i \oplus S) < a_i$，当前这堆石子就可以作为合法的必胜出发点。我们只需线性扫描所有石子堆，统计满足该代数不等式的数量即可。
C++ 标准源码
#include <iostream>
#include <vector>
// 解决经典 Nim 游戏状态判定与方案统计
void solve_nim_game(const std::vector<int>& piles) {
int nim_sum = 0;
for (int count : piles) {
nim_sum ^= count; // 计算全局尼姆和
}
if (nim_sum == 0) {
// 全局异或和为 0，先手必败
std::cout << "Second player wins (P-position)\n";
} else {
// 全局异或和不为 0，先手必胜
std::cout << "First player wins (N-position)\n";
int winning_moves_count = 0;
// 统计并输出先手可行的必胜走法数量
for (size_t i = 0; i < piles.size(); ++i) {
// 判断将这一堆修改为 piles[i] ^ nim_sum 是否合法（即数量变少）
if ((piles[i] ^ nim_sum) < piles[i]) {
winning_moves_count++;
}
}
std::cout << "Number of winning options for the first step: " << winning_moves_count << "\n";
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int t;
if (std::cin >> t) { // 多组测试数据
while (t--) {
int n;
std::cin >> n;
std::vector<int> piles(n);
for (int i = 0; i < n; ++i) {
std::cin >> piles[i];
}
solve_nim_game(piles);
}
}
return 0;
}
NOIP 实战避坑指南
- 混淆异或优先级与比较运算符优先级
在判断必胜走法时，核心表达式为
(piles[i] ^ nim_sum) < piles[i]。在 C++ 中，比较运算符（<）的优先级高于位运算符（^）。如果写成piles[i] ^ nim_sum < piles[i]，编译器会优先计算nim_sum < piles[i]得到一个bool值，再与前面的石子数做异或。这将导致彻底的逻辑崩溃。必须在外层强制加括号。 - 在 Nim 变式中盲目套用经典异或 许多题目会魔改 Nim 游戏的规则，例如“每次最多只能拿 $M$ 个石子”（巴什博弈结合）或“只能将石子移动到相邻的格子”（阶梯 Nim）。这些变式题的局势不再是纯粹的 $a_i$ 异或。例如阶梯 Nim 只需要异或奇数阶梯上的石子数。审题时必须看清移动的限制约束，切忌死记硬背。
经典 NOIP/洛谷 真题
1. 洛谷 P2197 【模板】Nim 游戏
- 题意描述：甲、乙两人玩 Nim 游戏。给定 $n$ 堆石子及每堆的数量，甲先手。若双方均采取最优策略，判断谁会获胜。
- 问题本质：标准 Nim 游戏 Bouton 定理的直接落地模板。
- 核心解题思路：直接将输入的 $n$ 个正整数执行全员
^（异或）累加。若最终结果为 $0$ 输出No（后手胜），否则输出Yes（先手胜）。
2. 洛谷 P1247 取火柴游戏
- 题意描述：在经典 Nim 游戏的基础上，题目要求：如果先手必胜，不仅要输出先手赢，还要输出先手第一步应该在第几堆拿走多少根火柴，使得丢给后手的是一个必败局。如果存在多种方案，输出堆号最小的。
- 问题本质：必胜策略的代数构造与具体路径输出。
- 核心解题思路：首先计算总异或和 $S$。若 $S \neq 0$，从 $1 \sim n$ 从小到大扫描每一堆火柴。只要遇到第一堆满足 $(a_i \oplus S) < a_i$ 的火柴堆，说明找到了堆号最小的合法方案。先手应该把这堆火柴削减为 $a_i' = a_i \oplus S$，即拿走的火柴数量为 $a_i - (a_i \oplus S)$。输出这堆的编号以及拿走的数量，直接终止程序。