这一类游戏可以用三句话定义清楚：两个人轮流走；每一步能走哪些只取决于当前局面（不看历史、不分身份，两人面对的选项完全相同）；走不动的人输。满足这三条的叫「公平组合游戏」（Impartial Combinatorial Game，下文写 ICG）。这一节只做一件事：给每个局面算出一个整数，用它一眼判断谁赢。
为什么算得出来？因为「必败」本身是递归定义的：走不动的局面必败；能一步走到必败局的局面必胜；所有后继都必胜的局面必败。这三句话从终点往前把整个局面图推了一遍，所以每个局面的胜负唯一确定，且只依赖它的后继。
| 局面 | 条件 | 结论 | 记号 |
|---|---|---|---|
| 无路可走（空局） | 没有合法步 | 必败 | P 态 |
| 存在一个后继是必败 | 至少一条路通向 P 态 | 必胜 | N 态 |
| 所有后继都是必胜 | 怎么走都把 N 态送给对方 | 必败 | P 态 |
先手推一个能一眼看穿的例子：一堆 n 个石子，每人每次取 1~3 个，取完者胜。n = 0 必败；n = 1、2、3 可以一次取完，必胜；n = 4 时无论取几个，都留给对方 3、2、1 个（全是必胜态），所以必败。照此推下去，胜负按 4 循环：必败 ⟺ n 是 4 的倍数。这个「先手的所有选择都把人送进必胜态，所以自己必败」的推理，就是整节的地基。
本节三块骨头：异或（Nim 判据的运算）、mex（SG 值的算法）、SG 定理（把任意 ICG 变成 Nim）。先把它们拆开看清。
| 组成 | 含义 / 格式要求 |
|---|---|
a ^ b | 逐位异或：同一位上两数相同得 0，不同得 1。5 ^ 3 = 101₂ ^ 011₂ = 110₂ = 6。 |
s ^= x | 把 x 异或进累积量，等价于 s = s ^ x。求全部堆的异或和只要这一个循环。 |
x ^ x = 0 | 自反：任何数异或自己得 0。所以「同一个数出现两次就抵消」，这是异或能表达「配对」的根源。 |
x ^ 0 = x | 0 是单位元。空局的异或和是 0，正好对上「走不动必败」。 |
交换律、结合律 | 异或和与堆的顺序无关，可以边读边算，不需要存数组。 |
没有进位 | 1 + 1 = 2，但 1 ^ 1 = 0。异或就是「不进位的加法」，各二进制位互不影响，所以下文的证明可以逐位讨论。 |
#include <bits/stdc++.h>
using namespace std;
int main() {
cout << (5 ^ 3) << "\n"; // 6
cout << (2 ^ 2) << "\n"; // 0：自己异或自己
cout << (1 ^ 1 ^ 1) << "\n"; // 1：奇数个 1 留下 1
int a[] = {1, 2, 3};
int s = 0;
for (int x : a) s ^= x;
cout << s << "\n"; // 0 → 这个局面先手必败
return 0;
}^ 的优先级低于 ==。写 if (s ^ a[i] == 0) 会被解析成 s ^ (a[i] == 0) —— 编译通过、含义全错 → WA。想判 s ^ a[i] 是否为 0，必须打括号。
异或能做的只有「判奇偶 / 配对 / 抵消」这一类事。看到「出现两次」「抵消」「按位独立」就要想起它。
| 组成 | 含义 / 格式要求 |
|---|---|
定义 | mex(S) = 最小的不属于 S 的非负整数。{0,1,3} → 2；{1,2} → 0；{} → 0；{0,1,2} → 3。 |
为什么需要它 | SG 值要回答「这个局面一步能走到哪些 SG 值」。能走到的集合是 S，最小的走不到的值就是当前局面的 SG —— 于是「能不能走到」被编码进了一个数。 |
实现思路 | 排序去重，然后从 0 开始扫：遇到第一个「断档」就停，那个缺口就是答案。 |
容量 | mex 一定不超过集合大小：k 个不同元素最多占住 0..k−1，第 k 个位置必然空着。所以标记数组开「后继个数 + 1」就够。 |
必须去重 | 重复元素不影响 mex，先 unique 再扫，逻辑最简单。 |
多组数据要清空 | 共用一个标记数组却忘记清零，上一组的标记会污染这一组 → WA，且只在大数据上错。 |
#include <bits/stdc++.h>
using namespace std;
int mex(vector<int> s) {
sort(s.begin(), s.end());
s.erase(unique(s.begin(), s.end()), s.end()); // 去重，顺序无关
int m = 0;
for (int x : s) {
if (x == m) ++m; // 0、1、2…… 连续被占住
else break; // 断档了，缺口就是答案
}
return m;
}
int main() {
cout << mex({0, 1, 3}) << "\n"; // 2
cout << mex({1, 2}) << "\n"; // 0
cout << mex({0, 1, 2}) << "\n"; // 3
return 0;
}负数不在 mex 定义域内。集合若是 {-1, 0}，答案仍是 1 —— 扫的时候把负数当成不存在。
mex 是算 SG 的唯一工具。记不住 SG 的定义时，记住「能走到的那些 SG 值组成集合，取 mex」就够了。
| 组成 | 含义 / 格式要求 |
|---|---|
怎么算 | SG 是 DAG 上的 DP：先算出所有后继的 sg，再取 mex。按「步数」或「数值」从小到大推。 |
初值 | 走不动的局面没有后继，集合为空，mex{} = 0。 |
单个游戏 | sg(x) = 0 ⟺ x 必败。这就是「一个整数代替一整个局面」的全部意义。 |
SG 定理 | 若干个互不干扰的子游戏同时进行时，整体必败 ⟺ 各子游戏 sg 值的异或和为 0。任意 ICG 的和都等价于一个 Nim。 |
Nim 是特例 | 一堆 n 个石子能走到 0..n−1 全部局面，它们的 sg 正好是 0..n−1，mex = n。所以单堆的 sg 就是石子数，异或和就是 Nim 判据 —— 不是巧合，是同一个定理。 |
打表找周期 | 后继的偏移量只有有限几种，sg 序列几乎总会很快进入周期。找到周期后，即使 n 到 10¹⁸ 也能 O(1) 算出来。 |
#include <bits/stdc++.h>
using namespace std;
int sg[35];
int main() {
for (int x = 1; x <= 30; ++x) {
bool seen[4] = {false}; // 后继只有 3 个，mex <= 3
for (int k = 1; k <= 3 && k <= x; ++k) // 可以取走 1、2、3 个
seen[sg[x - k]] = true;
int m = 0;
while (seen[m]) ++m;
sg[x] = m;
}
for (int x = 0; x <= 12; ++x) cout << sg[x] << " "; // 0 1 2 3 0 1 2 3 ...
return 0;
}seen 的下标是 SG 值，不是石子数。开多大取决于「后继个数」而不是 N。
取法变多时 seen 要跟着变大。保守写法是开 64，或者直接用 set（慢一点但不会越界）。
第一个能完整对上上面三块骨头的题就是 Nim 模板。它只有 12 行，但包含了整节的判据。
甲、乙两人玩 Nim 取石子游戏：地上有 n 堆石子，每人每次可从任意一堆里取出任意多枚丢掉，可以取完，不能不取，每次只能从一堆里取。最后没石子可取的人输。甲先手。
输入格式：本题有多组测试数据。第一行一个整数 T。接下来每两行是一组数据：第一行一个整数 n，表示有 n 堆石子；第二行 n 个非负整数，表示每堆的数量。
输出格式：共 T 行。若这组数据存在先手必胜策略，输出 Yes，否则输出 No。
数据范围：1 ≤ T ≤ 10，1 ≤ n ≤ 10⁴，每堆石子数不超过 2³¹ − 1。
暴力为什么不行。一个局面就是各堆数量构成的多重集，n = 10⁴ 时局面数是指数级的，不可能把状态图建出来。但每次只能让某一堆变小，这个偏序关系提示：胜负一定有一个 O(n) 的封闭判据。
先看一堆。先手一次取完，必胜。除了 n = 0，全是 N 态。
再看两堆 (a, b)。a = b 时必败：先手从一堆取走多少，后手就在另一堆取走同样多，局面永远回到「两堆相等」，最后一手一定属于后手。a ≠ b 时先手把多的那堆减到和少的相等，把必败态直接递过去。所以两堆的判据是「是否相等」。
猜。把「相等」翻译成二进制：a = b ⟺ a ^ b = 0。于是猜：所有堆异或和为 0 时先手必败。
证明只需两条，正好对应必败态定义的两个方向。
闭环。空局的异或和是 0 且必败，符合判据；上面两条说明「异或和 0 的局面只能走向非 0」「非 0 的局面总能走向 0」，与必败态/必胜态的递归定义逐条对齐，所以判据对任意局面成立。
复杂度。每组 O(n)，全部数据 O(Σn ≤ 10⁵)，就是一个异或循环。
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
long long s = 0; // 每组开头必须清零，否则会带上上一组的数据
for (int i = 0; i < n; ++i) {
long long x;
cin >> x;
s ^= x; // 边读边异或，不需要存数组
}
cout << (s ? "Yes" : "No") << "\n"; // s 非 0 → 先手必胜
}
return 0;
}| 代码片段 | 含义与理由 |
|---|---|
long long s = 0 | 异或的单位元。放在 while 内部，保证每组独立计算。 |
long long x; cin >> x | 每堆不超过 2³¹−1，用 long long 读，避开 int 上限附近的所有麻烦。 |
s ^= x | 把这一堆并进异或和。异或可交换，所以读取顺序无所谓。 |
cout << (s ? "Yes" : "No") | s 非 0 即必胜。三目运算符直接给出两种输出，不需要 if。 |
while (T--) | 跑 T 次，T 归零后结束。注意 T 被用掉了，循环里不能再拿它当数据范围。 |
不需要开数组 | 答案只依赖一个异或和，10⁴ 个数读完就能丢，空间 O(1)。 |
Nim 判据能成立，是因为「一堆 n 个」的 SG 值恰好等于 n。换句话说，Nim 的每一堆本身就是一个「等价于 n 个石子的游戏」。一旦取法改了，这个等价关系就断，判据必须换。
改一个字。同样的 n 堆石子，但每次只能取走 1、3、4 枚（取 2 枚不合法）。这时「一堆 n 个 = 一个数 n」不再成立：一堆 2 个只能取 1 枚，一堆 3 个能取到 0 或 2，它们能到达的局面集合和「n 个」完全对不上，异或判据直接用就错。
正确的做法分两步。第一步，只考虑单独一堆，用 mex 把它压缩成一个 SG 值 sg[n]；第二步，把所有堆的 sg 值异或起来，为 0 则必败。这就是 SG 定理，Nim 只是其中 sg[n] = n 的特例。
为什么可以先算单堆。各堆之间互不影响（每次只动一堆），所以整个游戏是「单堆游戏的直和」。SG 定理正是说：直和的 SG 值 = 各部分 SG 值的异或。
打表看形状。取法 {1,3,4} 的 sg 序列是 0, 1, 0, 1, 2, 3, 2, 0, 1, 0, 1, 2, 3, 2, 0, …，从 n = 1 起按 [1,0,1,2,3,2,0] 循环，周期 7。即 sg(n) = tab[(n−1) mod 7]（n ≥ 1）。
周期的用处。有了周期，n 到 10¹⁸ 也只要一次取模。这是博弈题最常见的提速手段：先打表 200 项，人眼找周期，再验证。验证的依据很硬：每一项只依赖前面 max(取法) 项，所以只要连续 T 项（T ≥ max(取法)）重复，后面的项就照抄前面的，自动循环下去。
#include <bits/stdc++.h>
using namespace std;
const int N = 60;
int sg[N];
int main() {
int mov[] = {1, 3, 4}; // 一次只能取走 1、3、4 枚
int cnt = 3;
for (int x = 1; x < N; ++x) {
bool seen[8] = {false}; // 后继最多 cnt 个，mex 不会超过 cnt
for (int j = 0; j < cnt; ++j)
if (mov[j] <= x) seen[sg[x - mov[j]]] = true; // 标记所有能到达的 sg
int m = 0;
while (seen[m]) ++m; // 找最小的缺口
sg[x] = m;
}
for (int x = 0; x < 30; ++x) cout << sg[x] << " \n"[x == 29];
// 输出：0 1 0 1 2 3 2 0 1 0 1 2 3 2 0 1 0 1 2 3 2 0 1 0 1 2 3 2 0 1
return 0;
}| 代码片段 | 含义与理由 |
|---|---|
mov[] = {1, 3, 4} | 合法的「一次取走数量」。改这一行就能换成任何取法，其余代码不动。 |
for (int x = 1; x < N; ++x) | 按 x 从小到大推。x 的后继是 x−mov[j]，都更小，所以一定已经算过。 |
if (mov[j] <= x) | x 不够取时这一步不合法，必须跳过；否则 sg[x - mov[j]] 的下标会变负 → RE。 |
seen[sg[x - mov[j]]] = true | 记下「能一步到达这些 sg 值」。注意下标是 sg 值，不是石子数。 |
while (seen[m]) ++m | 从 0 往上找第一个没被标记的数，就是 mex。 |
结束后的周期 | 从 n = 1 起 7 个一组循环。用 tab[(n-1) % 7] 就能 O(1) 算任意 n。 |
[x == 29] | 把布尔值当数组下标：最后一项取 '\n'，其余取空格，省掉一个 if。 |
上面所有结论都建立在 normal play（取走最后一枚的人赢）上。改成 misère play（取走最后一枚的人输，也就是反尼姆），Nim 判据整体失效：(1,1) 从必败变必胜，(1) 从必胜变必败。原因很直白——步数不再能任意拖长，最后一步成了负担。
| 局面 | 正常 Nim（最后一手赢） | 反尼姆（最后一手输） |
|---|---|---|
| 所有堆都不超过 1 枚 | 异或和 = 0 → 败 | 堆数为奇数 → 败 |
| 存在某堆至少 2 枚 | 异或和 = 0 → 败 | 异或和 = 0 → 败 |
| (1, 1) | 败 | 胜 |
| (1, 1, 1) | 胜 | 败 |
| (2, 2) | 败 | 败 |
| (1, 2) | 胜 | 胜 |
修正后的判据（SJ 定理）只有一句：先手必胜 ⟺ （所有堆都不超过 1 枚 且 异或和 = 0）或（存在某堆 ≥ 2 枚 且 异或和 ≠ 0）。
// s = 所有堆的异或和，big = 是否存在某堆 >= 2 枚
bool antiWin(long long s, bool big) {
if (!big) return s == 0; // 全是 0/1：偶数个 1 先手胜，奇数个 1 先手败
return s != 0; // 有大堆时，与正常 Nim 完全一致
}两类局面要分开讨论，是因为「最后一手输」只影响收尾阶段。只要场上还有一堆 ≥ 2，胜负手由异或和决定；等场上全是 1，就变成纯粹的奇偶问题，谁被迫拿走最后一枚谁输。
全零局面要按题目约定处理。反尼姆的递推把「无子可取」理解成上一手取走了最后一枚，所以函数对全零返回 true。若题目规定「初始为空则先手直接输」，就单独加一句判断——这类边界值不值得花时间争论，读题时看清约定即可。
用 sum 代替异或当判据 → WA。样例 (1,2,3) 的和是 6、异或和是 0，两种算法结论相反；小数据有可能碰巧对，大数据全错。
写成 if (s ^ a[i] == 0)：== 优先级高于 ^，编译通过但含义变成 s ^ (a[i] == 0) → WA。加括号，或者先存中间变量。
把 long long s = 0; 写在 while (T--) 外面 → 第二组起异或和混进了上一组的数据 → WA。症状非常典型：第 1 组对，后面全错。
用 int 存每堆石子。题目写「不超过 2³¹−1」，那就是 int 的上限 2147483647，边界值刚好踩在线上，换一道范围稍大的题立刻溢出。统一 long long，代价只是多 4 字节。
反尼姆里用 s <= 1 代替「所有堆都不超过 1」→ WA。反例：(2,3) 的异或和是 1，但它显然不是「全是 1」的局面。必须显式扫一遍看有没有 a[i] >= 2。
输出大小写不符。本题要 Yes／No，写成 YES 或 yes 一律 WA——评测是逐字节比对，不做智能匹配。
SG 打表时 seen 开小了。取法有 5 种时 mex 可能到 5，bool seen[4] 会越界写 → RE 或莫名其妙的 WA。开「取法数 + 1」。
关掉页面，把 P2197 那 20 行从零敲出来，提交确认样例输出 No / No / Yes。
改一改①：把 s ^= x 换成 s += x，只跑第 3 组 (1 2)：和是 3、异或和也是 3，两种算法都给 Yes，看不出区别。再跑 (1,1)：和是 2、异或和是 0，加法的答案变成 Yes，而正确是 No —— 亲手看到「判据必须是异或」。
改一改②：把 long long s = 0; 提到 while (T--) 上面再提交，观察第 2 组开始出错。这就是「多组数据没清零」的样子。
改一改③：把打表程序的 mov[] 改成 {1, 2}，重新跑，你会得到 0 1 2 0 1 2 …（周期 3），正好等于 n mod 3，和「一堆取 1~2 个必败 ⟺ n 是 3 的倍数」对上。
改一改④：在打表程序里把 seen 改成 bool seen[3]，mov 保持 {1,3,4}，观察结果是否开始出错。越界访问是未定义行为——它可能崩，也可能悄悄给出一个错误答案，而后者更危险。
异或的核心性质是逐位独立：第 k 位的结果只取决于所有数第 k 位上有多少个 1。偶数个 → 0，奇数个 → 1。所以「异或和 = 0」等价于「每一位上 1 的个数都是偶数」。
这条性质直接给出证明里的存在性：若 s = a₁ ^ … ^ aₙ ≠ 0，取 s 最高的那个 1，设它在第 k 位。第 k 位为 1 意味着「第 k 位上是 1 的堆有奇数个」，奇数 ≥ 1，所以至少有一堆的第 k 位是 1。
再看为什么 aᵢ ^ s < aᵢ。比较两个数的大小是从高位往下比的。s 的最高位是 k，所以高于 k 的位 s 全是 0，异或后不变；第 k 位上 aᵢ 和 s 都是 1，异或得 0。于是新数在最高的「有差异的位」上比原数小，整体就小。这一步是整个证明的枢纽：它保证取走 aᵢ − (aᵢ ^ s) > 0 枚，走法是合法的。
用代数的说法：所有非负整数在「异或」下构成一个 GF(2) 上的向量空间，每个数的每个二进制位是一个坐标，异或就是逐坐标相加。「异或和为 0」= 这 n 个向量线性相关到零向量，与顺序无关，这就是为什么堆可以任意排列。
SG 定理为什么成立。设两个子游戏 G₁、G₂ 的 SG 值为 g₁、g₂，要证 SG(G₁+G₂) = g₁ ^ g₂。分两步：
两条合起来：v 的后继都 ≠ v，而 0..v−1 全都可达，所以 mex 恰为 v。多个子游戏由归纳法合并即可。Nim 就是 gᵢ = 石子数的情形。
复杂度。Nim 判定 O(n)、空间 O(1)；SG 打表 O(N × 取法数)，N 为最大石子数。两者都是「一次线性扫描」的量级，真正的成本在于想清楚取法与周期。
seen 的大小为什么可以只开「取法数 + 1」而不是「最大石子数 + 1」？把这个结论说清楚，你就真正理解 mex 了。if (s ^ a[i] == 0) 错在哪，并写出正确写法。有 k 堆火柴，第 i 堆 nᵢ 根。两人轮流取，每次从某一堆取走若干根（可以取完整堆，不能不取，不能跨堆），谁取走最后一根谁获胜。你先手。
给定初始局面，判断先手是否必胜；若必胜，还要给出第一步该怎么取。
输入格式：第一行一个整数 k（k ≤ 5×10⁵）；第二行 k 个整数 n₁ … n_k（nᵢ ≤ 10⁹）。
输出格式：先手必败时输出一行 lose；必胜时第一行输出两个整数 a、b，表示从第 b 堆取出 a 根，第二行输出取完之后的 k 个整数（空格隔开）。有多种答案时输出 b 最小的（b 相同时 a 最小）。
胜负判据和例题完全一样，先把异或和算出来；为 0 就是 lose。
必胜时，第一步必须把局面送到「异或和为 0」。想让第 i 堆变成多少？只可能是一个唯一的值。
从第 1 堆开始往后扫，第一个「能被改小」的堆就是答案要求的 b——因为 b 要最小。别忘了输出取完之后的整副牌。
设 s = n₁ ^ n₂ ^ … ^ n_k。s = 0 时先手必败，直接输出 lose。
s ≠ 0 时，由 Nim 的证明，一定存在堆 i 满足 nᵢ ^ s < nᵢ。把第 i 堆改成 nᵢ ^ s，新的异或和就是 s ^ nᵢ ^ (nᵢ ^ s) = 0，把必败态送给了对方。
要取多少根：取走 nᵢ − (nᵢ ^ s) 根。这个数一定为正，因为 nᵢ ^ s < nᵢ。
为什么最小的 b 就够：要让异或和归零，其余 k−1 堆不动时，第 i 堆的新值被唯一确定为 nᵢ ^ s。所以「b 固定」时取法只有一个，题目要求的「b 最小优先、a 其次」就退化成「找第一个合法的 i」。
复杂度：找 i 是 O(k)，输出是 O(k)，总 O(k)，k = 5×10⁵ 完全够。数组要开到 5×10⁵ 以上。nᵢ ≤ 10⁹ 用 int 也装得下，但统一 long long 能省掉「这里要不要转换」的思考成本。
#include <bits/stdc++.h>
using namespace std;
const int N = 500005;
int k;
long long a[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> k;
long long s = 0;
for (int i = 1; i <= k; ++i) { cin >> a[i]; s ^= a[i]; }
if (s == 0) { // 异或和为 0：先手没有必胜走法
cout << "lose\n";
return 0;
}
for (int i = 1; i <= k; ++i) {
if ((a[i] ^ s) < a[i]) { // 第 i 堆能变到 a[i]^s，并且确实变小了
long long take = a[i] - (a[i] ^ s);
a[i] ^= s; // 改完后全局异或和变 0
cout << take << " " << i << "\n";
for (int j = 1; j <= k; ++j) cout << a[j] << " \n"[j == k];
return 0;
}
}
return 0;
}| 片段 | 作用 |
|---|---|
s ^= a[i] | 边读边算异或和。判据只需要这一个量。 |
if (s == 0) { cout << "lose"; return 0; } | 必败局没有第一步可输出，直接结束。注意不是输出 0。 |
(a[i] ^ s) < a[i] | 同时完成两件事：检查这一堆能不能改小（合法性），以及保证找到的是最小的 i。a[i] = 0 时右边是 s > 0，条件不成立，自动跳过空堆。 |
take = a[i] - (a[i] ^ s) | 取走的根数。因为 a[i]^s 严格小于 a[i]，这个数一定为正。 |
a[i] ^= s | 先改再输出，否则打印的是原始局面。这一步就是把异或和清零。 |
cout << take << " " << i | 题目要的是「数量 堆号」，顺序反了就 WA。 |
" \n"[j == k] | 最后一项输出换行、其余输出空格，避免行末多一个空格。 |
sum 或者干脆只比大小：样例恰好能过，提交全 WA。a[i] ^= s，把原始局面输出了 → WA，而且第一行是对的，很难发现。a b，a 是取走的根数。(a[i] ^ s) < a[i] 写成 a[i] > s：两者完全不等价，会挑到不合法的堆，改完异或和不为 0 → WA。Lose 或 lose （多了空格）→ WA，逐字节比对。