SG函数打表的核心目的是发现状态转移的周期性或分段规律，而非单纯计算SG值；需确保规则确定、无环、有限后继，并用bitset高效实现mex，结合观察循环节、模分组、稀疏零点三类现象分析规律。
SG函数打表的核心目的不是算值，而是发现状态转移的周期性或分段规律
直接暴力递归求每个状态的 sg() 很容易超时或栈溢出，尤其当状态数大（比如石子数 up to 1e5）时。打表的本质是把 sg[i]（i 从 0 到 N）全算出来，然后肉眼或辅助观察找 pattern——比如是否出现循环节、是否按模某个数分组、是否存在“必败态稀疏分布”等。
关键前提是：游戏规则必须是**确定性、无环、有限后继**的公平组合博弈，且每个状态的后继状态能用简单规则生成（如每次可取 1/2/5 颗石子）。
实操建议：
- 先写一个基础
sg()记忆化递归函数，仅用于验证小范围（0~50）结果是否合理 - 再改写为自底向上递推的打表版本，避免递归开销和栈限制
- 打印时带上索引，例如：
i=0, sg=0、i=1, sg=1……方便对齐观察 - 把输出重定向到文件，用文本工具（如 VS Code）开启列选择或正则高亮，快速扫视重复块
怎么写安全高效的 SG 打表代码（C++）
常见错误是没正确实现 mex（minimum excludant）计算，或忽略状态不可达导致的数组越界。以下是最简可靠模板：
立即学习“C++免费学习笔记（深入）”；
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
#include <vector>
#include <bitset>
#include <iostream>
using namespace std;
<p>const int MAXN = 10005;
int sg[MAXN];
bitset<MAXN> vis; // 比 bool[] 快，且自动清零</p><p>// moves 是合法操作集合，如 {1,2,5}
vector<int> moves = {1,2,5};</p><p>void precalc_sg(int n) {
sg[0] = 0; // 终止态
for (int i = 1; i <= n; ++i) {
vis.reset();
for (int d : moves) {
if (i - d >= 0) {
vis[sg[i-d]] = true;
}
}
int j = 0;
while (vis[j]) ++j;
sg[i] = j;
}
}</p>注意点：
-
vis用bitset而非vector<bool>，避免动态 resize 和迭代器失效风险 - mex 求解必须从 0 开始线性扫描，不能用 set 或 sort —— 因为 SG 值通常很小（一般 ≤ moves.size()），暴力扫更快更稳
- 如果 moves 中有大于 i 的数，直接跳过，不判
i-d < 0会越界 - 若规则含“必须取满某条件”（如“只能在石子数为偶数时取 3 颗”），则需在内层加额外判断，不能只靠
i-d >= 0
怎么看出来的规律？重点盯这三类现象
打完 sg[0..100] 后，不要逐个读数字，而是按以下方式扫描：
-
循环节：复制前 20 个值，粘贴多次，看是否出现重复段。例如
0,1,2,0,1,2,...→ 周期为 3；用 Python 脚本可快速检测最小循环节长度 -
模意义分段：把
i % k相同的位置 SG 值列成一列，看是否恒定。常见于“每次可取 1~m 颗”类问题，结果常为i % (m+1) -
稀疏零点：记录所有
sg[i] == 0的 i，看是否满足某种公式（如平方数、斐波那契数、2 的幂）。必败态往往比必胜态少得多，更容易看出结构
举个例子：若 moves = {1,3,4}，打表发现 sg[i] 序列为 0,1,0,1,2,3,2,3,4,5,4,5,...，这时要怀疑“奇偶分治”或“每 7 个一循环”——实际这个序列周期确实是 7。
打表失败的典型信号及应对
如果你打了 200 项还看不出规律，大概率是下面某个问题：
-
moves定义错：比如写成{1,2,2}（重复值未去重），导致 vis 标记混乱；务必用set初始化或手动 dedup - 状态定义不完整：比如 Nim 变种中“两堆石子，每次从一堆取”，状态应是二维
(a,b)，但你只打了sg[i]一维——此时必须转为二维打表或用 Grundy 数异或性质降维 - SG 值增长过快：若
sg[100]已达 50+，说明 mex 不收敛，大概率规则含“可取任意奇数颗”之类无限分支，这种问题通常无法靠打表找简单规律，需换思路（如证明 SG 值等于二进制最低位 1 的位置） - 忘了清空
vis：C++ 中bitset::reset()必须每轮调用，否则上一轮标记残留会导致 mex 错误
真正难的不是打表本身，而是判断该问题是否适合打表——有些博弈的 SG 序列看似随机，实则是伪随机，强行找规律只会浪费时间。先确认规则是否足够“规整”，再决定要不要继续扩大 N。
