[学习笔记] 公平组合博弈全家桶：从 SG 本质到经典模型
TAG: 博弈论, 公平组合博弈, SG函数, Sprague-Grundy定理, ACM
本文默认读者已经掌握公平组合博弈（Impartial Game）的基本概念、Nim 的异或结论以及 SG 函数的定义。本文不从零介绍，而更关注 SG 为什么成立、规则变化后应该看什么、常见模型如何快速识别，以及这些结论在竞赛题里怎样落地。
记号约定：若无特殊说明，均为有限、无随机、Normal Play 的无偏博弈；
P-position表示先手必败态，N-position表示先手必胜态。
目录
- 题目总索引
- Part 0. SG 函数的本质
- 0.0 常见 SG 打表模板
- 0.1 SG 值到底是什么
- 0.2 为什么是 mex
- 0.3 游戏和为什么做 xor
- 0.4 什么规则改动会改变 SG
- 0.5 猜出 SG 闭式以后怎么证明
- Part 1. SG 扩展体系
- 1.1 Anti-SG 与 SJ 定理
- 1.2 SG 在 DAG、树、图上的落地
- 1.3 Multi-SG
- 1.4 Every-SG
- Part 2. 线性移动博弈
- 2.1 Nimble
- 2.2 Welter Game
- 2.3 Silver Dollar Game
- 2.4 Staircase Nim
- Part 3. 分裂型博弈
- 3.1 统一结构
- 3.2 Kayles
- 3.3 Dawson's Kayles
- Part 4. 数学结构型博弈
- 4.1 Wythoff Nim
- 4.2 同步减法类：Take Apples
- Part 5. 结构性胜负与策略窃取
- 5.1 不要见到博弈就硬算 SG
- 5.2 Chomp 与 Strategy Stealing
- 5.3 因子偏序上的高维 Chomp
- 5.4 Independent Nim：一个“不能拆成独立子游戏”的反例
- 最后：模型识别速查表
题目总索引
下面只保留 能够代表一个模型、能够体现关键转化、或者本身足够有训练价值 的题，不为了数量堆题。
| 模块 | 题目 | 关键词 | 定位 |
|---|---|---|---|
| Part 0 | Codeforces 2240C - Nim Game Is XOR Game | P/N 刻画、xor、计数 | 综合题 / 个人做题记录筛选 |
| Part 1 | POJ 3480 - John | Anti-Nim、Misère Nim | 模板题 |
| Part 1 | POJ 2425 - A Chess Game | DAG SG、多棋子 xor | 模板题 |
| Part 1 | POJ 2311 - Cutting Game | Multi-SG、切割 | 模板题 |
| Part 1 | HDU 3595 - GG and MM | Every-SG、step | 模板题 |
| Part 1 | Petrozavodsk Camp G - Remove the Prime | 质因子拆分、连续段、Multi-SG | 高质量转化题 |
| Part 2 | 飞翔的甲鱼 | Welter Function | Welter 主例题，题面截图 |
| Part 2 | POJ 1704 - Georgia and Bob | Silver Dollar、相邻配对 | 模板题 |
| Part 2 | LOJ 5096 - 鹅卵石 Pebbles / Luogu P3480 | 差分、Staircase Nim | 高质量转化题 |
| Part 3 | POJ 3537 - Crosses and Crosses | 区间分裂、SG 周期思想 | 模板题 |
| Part 3 | 2025 CCPC Online F - 连线博弈 | 分裂 SG、周期 34、随机 Hash | 综合题 |
| Part 4 | POJ 1067 - 取石子游戏 | Wythoff、Beatty 序列 | 模板题 |
| Part 4 | Nowcoder NC26003 - Take Apples | 同步减法、P-position 构造 | 结论题 |
| Part 5 | Chomp | Strategy Stealing | 经典模型 |
| Part 5 | 因子偏序高维 Chomp | 偏序格、质因数指数向量 | 拓展题 |
| Part 5 | AtCoder ARC225 B - Independent Nim | 同一步跨多个区间、P-position 构造 | 综合题 / 个人做题记录筛选 |
公开做题记录中额外筛入了
CF 2240C和ARC225 B：它们不是为了凑“博弈题数量”，而是分别能很好体现 “SG 与单纯 P/N 判定不是一回事”、“看起来被 0 分隔也未必是独立子游戏” 两个很容易犯的错误。
Part 0. SG 函数的本质
这一部分不重新讲“什么是公平博弈”，只把后文真正反复使用的 SG 思想压缩出来。
0.0 常见 SG 打表模板
竞赛里遇到陌生小状态博弈，最可靠的第一反应通常不是猜公式，而是：先把 SG 打出来，再观察规律。
模板 1：时间戳 mex
如果后继 SG 数量不大，用 vis + 时间戳 比每次开 set 更轻。
SG / mex 基础模板
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int M=4096;
int vis[M],tim;
int mex(const vector<int>&v){++tim;for(int x:v) if(x<M) vis[x]=tim;int g=0;while(vis[g]==tim) g++;return g;
}
M 只需要大于你能证明的最大 mex。若一个状态最多只有 d 种不同后继，则显然有 SG<=d，这通常能给出很小的数组上界。
模板 2：DAG 上记忆化 SG
状态 u├──> v1├──> v2└──> v3
直接：
DAG SG 模板
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N=2e5+10;
int sg[N],vis[N],tim;
vector<int>g[N];
int dfs(int u){if(sg[u]!=-1) return sg[u];vector<int>v;for(int x:g[u]) v.push_back(dfs(x));++tim;for(int x:v) if(x<N) vis[x]=tim;int t=0;while(vis[t]==tim) t++;return sg[u]=t;
}
模板 3：一次操作把游戏裂成多个部分
若一步操作得到：
那么这一种操作对应的后继 SG不是某一个子状态，而是：
所以常见区间递推长成：
for(int cut=...;cut...;cut++)nxt.push_back(sg[left]^sg[right]);
sg[len]=mex(nxt);
后面的 Multi-SG、Kayles、连线博弈本质都在反复用这一句。
模板 4：打表找周期
很多一维有限规则博弈会出现 SG 周期，但看见前 20 项重复绝不能直接当证明。竞赛里若题目本身允许经验找规律，至少应：
- 暴力算到几百 / 几千项；
- 找候选周期
p； - 在足够长的后缀上验证
sg[i]=sg[i-p]； - 若要写严谨题解，再补“为什么之后的转移窗口完全相同”的周期证明，或者引用已有经典结论。
0.1 SG 值到底是什么
SG 最容易被错误理解成“局面的强弱分数”。实际上：
这里 *x 表示一堆大小为 x 的 Nim。也就是说，SG 值是在组合游戏意义下给局面划分 Nim 等价类的编号：无论以后把 G 和什么其他公平游戏相加，G 的作用都与一堆 SG(G) 个石子的 Nim 完全相同。
因此 SG=1 和 SG=100 单独看都是先手必胜，却绝不是同一种局面。若再加一个 SG=1 的游戏：
前者变成必败，后者仍然必胜。P/N 只保留“是否为 0”这一位信息，SG 才保存了足以进行组合的信息。
0.2 为什么是 mex
定义：
若 SG(G)=g，mex 的真正信息只有两句：
而大小为 g 的 Nim 堆恰好能走到 0,1,...,g-1，却不能一步回到 g。因此普通游戏只要拥有相同的“nimber 可达结构”，在组合意义下就与 *g 等价。这也是后面证明 Staircase Nim、Welter Function 等闭式时最应该抓住的东西，而不是机械背 mex 三个字母。
0.3 游戏和为什么做 xor
若一次只能选择其中一个独立子游戏进行操作：
Sprague-Grundy 定理给出：
原因并不是“SG 规定要异或”，而是每个 G_i 都先等价成 Nim 堆 *g_i，而 Nim 堆的和本身恰好满足 xor 运算。
这里最重要的前提是 独立：一步只能动一个子游戏，且对子游戏 A 的操作不会改变 B 的合法操作集合。很多题最难的并不是算 SG，而是判断“你以为的两个部分到底是不是独立子游戏”。
0.4 什么规则改动会改变 SG
设当前后继 SG 集合为 S，且：
若只对当前节点增删边，并且那些后继节点自己的 SG 不变，那么：
- 新增一个到
h<g的操作：没影响，因为h本来就必须存在； - 新增一个到
h>g的操作：没影响； - 新增一个到
h=g的操作：一定改变当前 SG； - 删除一个
h>g的后继：没影响； - 删除
h<g的后继：只要仍有其他操作能到h就没影响；若删掉了最后一个h，SG 会改变。
所以：
这也解释了为什么 Staircase Nim 中“偶数层向奇数层搬、让有效堆增大”这种普通 Nim 没有的操作并不会破坏结论：它增加了额外后继，但始终没有破坏“所有小值可达、自己不可达”的结构。
注意：如果你修改的是全局规则，后继状态自己的 SG 也可能递归改变，此时不能只看当前节点新增的那一条边，而必须重新检查整个状态图。
0.5 猜出 SG 闭式以后怎么证明
以后若通过打表猜出：
最通用、最短的证明模板就是：
对任意状态
S，先证明任何合法操作S->T都满足F(T) != F(S)；再证明对每个0<=x<F(S)，总能找到一个合法后继T使F(T)=x。于是后继F值包含0..F(S)-1而不包含F(S)，根据 mex 定义即有SG(S)=F(S)。按照游戏 DAG 的拓扑序归纳即可。
这一段几乎就是 Nim、Staircase Nim、Welter Function 等很多闭式 SG 证明的共同骨架。
例题：Codeforces 2240C - Nim Game Is XOR Game
题目：https://codeforces.com/contest/2240/problem/C
这题不是标准 Nim：一次选择一个非零向量 b，满足 0<=b_i<=a_i 且所有 b_i 的 xor 为 0，再令 a_i-=b_i，问第一步有多少种能保证获胜的选择。
关键先不算 SG，而是刻画 P/N：局面中非零数不超过一个时为 P-position；非零数至少两个时为 N-position。 因此“第一步获胜”就是一步把局面变成只剩至多一个非零数。设总 xor 为 S：若 S=0，只有把全部数一次删完这一种；否则若最终只留下第 i 个数，则它必须变成 S xor a[i]，合法条件正是 (S xor a[i])<a[i]。这题很适合提醒自己：有时题目只要求 P/N 或 winning move 数量，并不需要完整 SG。
参考代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
void solve(){int n;cin>>n;vector<int>a(n);int s=0;for(int&i:a) cin>>i,s^=i;if(n==1){cout<<0<<endl;return;}if(s==0){cout<<1<<endl;return;}int ans=0;for(int x:a) if((s^x)<x) ans++;cout<<ans<<endl;
}
signed main(){ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin>>T;while(T--) solve();return 0;
}
Part 1. SG 扩展体系
普通 SG 的核心前提是：Normal Play、一次只选择一个独立子游戏操作。规则一旦改变，首先应该问的不是“还能不能 xor”，而是 到底改坏了 SG 定理的哪一个前提。
本部分主要参考：贾志豪《组合游戏略述——浅谈 SG 游戏的若干拓展及变形》：
GitHub PDF 镜像
1.1 Anti-SG 与 SJ 定理
Anti-SG
Anti-SG 把终局规则反过来：
最熟悉的特例就是 Misère Nim（拿走最后一颗石子的人输）。
Misère Nim 结论
设石堆为 a_1,...,a_n。
- 若存在某一堆
a_i>1，结论与普通 Nim 的 P/N 判定一致：
- 若所有非空堆大小都为
1，则只看非空堆数量：
原理只需记一句：当存在大堆时，胜手可以把游戏控制到“奇数个 1 交给对方”的尾局；一旦全部进入 1 的区域，普通 xor 已经退化成数量奇偶，而 Misère 正好把终局奇偶翻转。
SJ 定理
Anti-Nim 的结论不能直接无条件推广到任意 Anti-SG 游戏和。SJ 定理需要额外终止条件：
当所有单一游戏的 SG 值都变成
0时，整个游戏结束。
在此前提下，先手必胜当且仅当满足下面两种情况之一：
- 总 xor 不为
0，并且至少有一个子游戏SG>1； - 总 xor 为
0，并且所有子游戏SG<=1。
也就是：
其中：
易错点：不要看到“最后一步输”就把所有子游戏 SG 算出来后机械套上面两条。SJ 定理的附加终止条件是结论成立的关键；普通 Misère Nim 恰好满足更强的特殊结构，所以有大家熟悉的简洁结论。
例题：POJ 3480 - John
题目：https://poj.org/problem?id=3480
标准 Misère Nim。若至少有一堆大于 1，按普通 Nim 看 xor；否则所有堆都是 1，看堆数奇偶即可。
参考代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
void solve(){int n;cin>>n;int xr=0;bool big=0;for(int i=1,x;i<=n;i++){cin>>x;xr^=x;if(x>1) big=1;}if(big) cout<<(xr?"John":"Brother")<<endl;else cout<<(n%2==0?"John":"Brother")<<endl;
}
signed main(){ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin>>T;while(T--) solve();return 0;
}
1.2 SG 在 DAG、树、图上的落地
DAG：最标准的 SG 状态图
只要每个状态的合法转移组成 DAG，就直接按拓扑关系定义：
若有多个互不影响的棋子分别位于 u_1,...,u_k，总局面就是这些单棋子游戏的和：
树：根树删边 / Green Hackenbush 的经典形式
一棵以 u 为根的树，每次删一条边，所有与根断开的部分同时消失。设 v 为 u 的儿子，则：
为什么是 +1？从 u 到某个儿子 v 的整条分支，相当于在 v 的游戏上方再串了一条可以直接砍断的边；不同儿子分支之间独立，于是最后 xor。
一般图要谨慎
“图上博弈”不等于“直接对顶点做 SG”。如果原图有环，状态可能出现回到旧状态、和局、重复局面等，普通 SG(u)=mex(...) 的 DAG 递归未必成立。竞赛中常见的正确做法是：
- 原图本身就是 DAG；或
- 虽然棋盘有环，但完整游戏状态按某个势函数严格下降，因此状态图仍是 DAG；或
- 题目另有专门的环缩并 / 图博弈定理。
不要只因为题目出现“图”就机械套 SG。
例题：POJ 2425 - A Chess Game
题目：https://poj.org/problem?id=2425
给定 DAG，多枚棋子可以重合，每次只选择一枚棋子沿一条有向边移动。单枚棋子位于 u 的 SG 就是 sg[u]；每枚棋子互不影响，因此查询时把所有起点 SG xor 即可。
参考代码
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N=1005;
vector<int>g[N];
int sg[N];
int dfs(int u){if(sg[u]!=-1) return sg[u];bool vis[N]={0};for(int v:g[u]) vis[dfs(v)]=1;int x=0;while(vis[x]) x++;return sg[u]=x;
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n;while(cin>>n){for(int i=0;i<n;i++){g[i].clear();int k;cin>>k;while(k--){int v;cin>>v;g[i].push_back(v);}}memset(sg,-1,sizeof(sg));int m;while(cin>>m&&m){int xr=0;while(m--){int u;cin>>u;xr^=dfs(u);}cout<<(xr?"WIN":"LOSE")<<endl;}}return 0;
}
1.3 Multi-SG
普通 SG 中，一个单一游戏一步后还是一个单一游戏。Multi-SG 允许：
那么这一次操作对应的后继 nimber 就是：
父状态仍然对所有合法操作的后继 nimber 做 mex。换句话说，Multi-SG 并没有推翻 Sprague-Grundy，而只是允许“一次操作产生多个独立子游戏”。
这和普通 DAG SG 要区分：DAG 上的 u->v 只是一个状态变成另一个状态；Multi-SG 的关键是 u -> v_1+v_2+...。
例题：POJ 2311 - Cutting Game
题目：https://poj.org/problem?id=2311
切一块 w*h 的纸，一刀以后产生两块独立矩形，于是某个竖切位置 k 的后继为：
横切同理。题目中若一刀直接得到 1*1 当前玩家立即获胜，所以在转换成普通 SG 时，只枚举两边宽度都至少为 2 的“继续游戏”切法；能直接制造 1*1 的情况已经属于即时胜利，不应该再当普通后继继续递归。
参考代码
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
int sg[205][205];
int dfs(int n,int m){if(n>m) swap(n,m);if(sg[n][m]!=-1) return sg[n][m];bool vis[512]={0};for(int i=2;i<=n-2;i++) vis[dfs(i,m)^dfs(n-i,m)]=1;for(int i=2;i<=m-2;i++) vis[dfs(n,i)^dfs(n,m-i)]=1;int g=0;while(vis[g]) g++;return sg[n][m]=g;
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);memset(sg,-1,sizeof(sg));int n,m;while(cin>>n>>m) cout<<(dfs(n,m)?"WIN":"LOSE")<<endl;return 0;
}
例题：G. Remove the Prime
题目：2020-2021 Winter Petrozavodsk Camp, Day 5, G - Remove the Prime
一次选一个质数 p 和一段连续区间，要求区间内每个数都能被 p 整除，然后把这一段中所有数的 p 因子全部去掉。
最关键的拆分是：不同质数互不影响。 固定一个质数 p，只看哪些位置当前含有 p。每个极大连续 1 段就是一个独立游戏；一次选子段把它删掉，会把长度 L 的段裂成左右两个段。这个“任取一个非空子段删除”的游戏打表可得且能直接证明：
于是答案就是：对每个质数，把它出现位置的所有极大连续段长度 xor 起来，再把所有质数的结果继续 xor。真正的工程难点反而变成 a_i<=10^{18} 的快速质因数分解，因此使用 Miller-Rabin + Pollard-Rho。
参考代码（Miller-Rabin + Pollard-Rho）
#include<bits/stdc++.h>
using namespace std;
using ull=unsigned long long;
using u128=__uint128_t;
#define endl '\n'
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ull mul(ull a,ull b,ull mod){return (u128)a*b%mod;}
ull qpow(ull a,ull b,ull mod){ull ans=1;while(b){if(b&1) ans=mul(ans,a,mod);a=mul(a,a,mod);b>>=1;}return ans;
}
bool isprime(ull n){if(n<2) return 0;for(ull p:{2ULL,3ULL,5ULL,7ULL,11ULL,13ULL,17ULL,19ULL,23ULL,29ULL,31ULL,37ULL}){if(n%p==0) return n==p;}ull d=n-1,s=0;while(!(d&1)) d>>=1,s++;for(ull a:{2ULL,325ULL,9375ULL,28178ULL,450775ULL,9780504ULL,1795265022ULL}){if(a%n==0) continue;ull x=qpow(a%n,d,n);if(x==1||x==n-1) continue;bool ok=0;for(ull r=1;r<s;r++){x=mul(x,x,n);if(x==n-1){ok=1;break;}}if(!ok) return 0;}return 1;
}
ull nxt(ull x,ull c,ull mod){return (mul(x,x,mod)+c)%mod;}
ull rho(ull n){if(n%2==0) return 2;if(n%3==0) return 3;while(1){ull c=rng()%(n-1)+1;ull x=rng()%(n-2)+2,y=x,d=1;while(d==1){x=nxt(x,c,n);y=nxt(nxt(y,c,n),c,n);ull z=x>y?x-y:y-x;d=gcd(z,n);}if(d!=n) return d;}
}
void factor(ull n,vector<ull>&v){if(n==1) return;if(isprime(n)){v.push_back(n);return;}ull d=rho(n);factor(d,v);factor(n/d,v);
}
void solve(){int n;cin>>n;unordered_map<ull,int> last,len;ull xr=0;for(int i=1;i<=n;i++){ull x;cin>>x;vector<ull>fac;factor(x,fac);sort(fac.begin(),fac.end());fac.erase(unique(fac.begin(),fac.end()),fac.end());for(ull p:fac){if(last[p]==i-1) len[p]++;else{if(last[p]) xr^=(ull)len[p];len[p]=1;}last[p]=i;}}for(auto [p,l]:len) xr^=(ull)l;cout<<(xr?"First":"Second")<<endl;
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);solve();return 0;
}
这题真正值得留下来的不是 Pollard-Rho，而是第一步：把“操作某个质数”识别成按质数完全独立的子游戏，再把每个质数拆成连续段游戏。
1.4 Every-SG
Every-SG 的规则与普通游戏和恰好相反：
对于所有还没有结束的单一游戏，当前玩家这一回合都必须各走一步。
因此 xor 不再是核心。现在真正决定整体何时结束的是：哪个子游戏拖得最久，以及胜手/败手分别希望它拖长还是尽快结束。
对一个单一状态 v 定义 step(v)：
含义是：
- 当前是必胜态时，胜手会在能走向必败态的方案中尽量拖长；
- 当前是必败态时，对手最终能控制结果，因此当前一方只能按最短结束来衡量。
Every-SG 定理：
并且单个游戏中，N-position 的 step 必为奇数，P-position 的 step 必为偶数。直觉上，最长的那个子游戏最后一个结束，它的步数奇偶直接决定谁做最后一次全局操作。
例题：HDU 3595 - GG and MM
题目：https://acm.hdu.edu.cn/showproblem.php?pid=3595
每个单一游戏给两个数 (x,y)，一次从大数中减去小数的正整数倍；全局每一回合必须对所有未结束的单一游戏各操作一次，正是 Every-SG。
对单局做欧几里得递归。若 y/x=1，当前只有一种商层级，胜负翻转且 step+1；若 y/x>1，当前玩家可以通过选择减几倍来控制后继奇偶，因此当前一定是 N-position，并能由后继信息求出最长 step。最后只取所有单局 step 的最大值判奇偶。
参考代码
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N=1005;
int sg[N][N],st[N][N];
int dfs(int x,int y){if(x>y) swap(x,y);if(sg[x][y]!=-1) return sg[x][y];if(x==0||y==0) return sg[x][y]=st[x][y]=0;int r=y%x,k=y/x;if(k==1){sg[x][y]=dfs(r,x)^1;st[x][y]=st[min(r,x)][max(r,x)]+1;}else{int t=dfs(r,x);st[x][y]=t+st[min(r,x)][max(r,x)]+1;sg[x][y]=1;}return sg[x][y];
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);memset(sg,-1,sizeof(sg));int n;while(cin>>n){int ans=0;for(int i=1;i<=n;i++){int x,y;cin>>x>>y;if(x>y) swap(x,y);dfs(x,y);ans=max(ans,st[x][y]);}cout<<(ans&1?"MM":"GG")<<endl;}return 0;
}
Part 2. 线性移动博弈
这一类题最值得形成“规则辨认链”：
可以任意向左，允许跨越、允许重合 -> Nimble
可以任意向左，允许跨越、禁止重合 -> Welter
可以任意向左，禁止跨越、禁止重合 -> Silver Dollar
按相邻层向出口移动 -> Staircase Nim
规则只改一条，SG 结构可能完全不同。
2.1 Nimble
棋子位于 x_1,...,x_n，一次任选一枚向左移动任意距离，允许跨过其他棋子，也允许落在同一位置。棋子之间完全独立，所以每枚位置 x_i 就是一堆大小为 x_i 的 Nim：
这个模型本身没必要展开，真正值得记的是下面两次“加限制”会发生什么。
2.2 Welter Game
模型
格子编号：
若干硬币占据互不相同的位置 a_1,...,a_n。每次选择一个硬币移动到任意更小的空位置：允许跨越其他硬币，但不允许重合。
它可以理解成：
Nimble + “所有 Nim 堆大小必须互不相同”。
正是这一个“禁止重合”，让单纯的位置 xor 失效。
Welter Function
对不同的 x,y，定义 mating function：
因为若 d=|x-y|，则：
于是 Welter Function 为：
Welter 定理：
怎么记这个修正项
Nimble 原来只有：
Welter 多出来的是所有棋子对的“碰撞修正”。若：
说明两位置的二进制低 t 位相同、第 t 位才第一次不同，于是这一对贡献：
恰好翻转第 0..t 位。Welter 的修正只关心两位置在二进制低位上“粘了多久”。 这比死背一个 d xor (d-1) 更容易记。
最精髓的证明思路
把 W 当成候选 SG。Welter Function 对任意一个坐标都是所谓 animating function：固定其他硬币后，目标 nimber 唯一决定这个坐标应该变到哪里；若目标 s'<s=W，总能找到至少一个坐标需要向左减小，从而覆盖所有 0..W-1。另一方面合法地只移动一枚硬币不可能保持 Welter Function 不变，因此 W 自己不可达。正好满足 mex 的两个条件，所以 W=SG。
论文 / 资料
Welter 部分建议直接看下面几篇：
- Tomoaki Abuku, Transfinite Version of Welter's Game
arXiv 页面 / PDF
其中第 1.3 节完整整理了普通 Welter Game、mating function、Welter Function，并在 Theorem 1.17 给出Grundy = Welter Function。 - Yuki Irie, p-Saturations of Welter's Game and the Irreducible Representations of Symmetric Groups
arXiv 页面 / PDF - Yuki Irie, A p-calm game and Welter's game
arXiv 页面 - C. P. Welter, The theory of a class of games on a sequence of squares, in terms of the advancing operation in a special group, 1954（原始论文）
DOI
现代阅读建议以上面的 Abuku 论文为主：原论文记号较老，而 Abuku 的第 1.3 节已经把普通 Welter Game 与 Welter Function 用现代 SG 语言重新整理。
例题：飞翔的甲鱼
题意就是标准 Welter：格子从 1 开始编号，每只甲鱼可以飞到任意更小且没有甲鱼的位置，可以跨过其他甲鱼。先把位置全部减一变成 Welter 标准的 0 起点，然后计算 Welter Function，非零即先手胜。
直接按所有棋子对计算是 O(n^2)。还可以利用：修正项的第 b 位为 1 当且仅当一对位置满足：
因此第 b 位只需统计“模 2^b 相同的数对个数的奇偶”。把 32 位整数按位反转后排序，原数低 b 位相同就变成排序后公共前缀相同；对每个 b 扫描所有组，C(cnt,2) 的奇偶即 (cnt>>1)&1。这样可以把公式计算到 O(n\log n+31n)。
说明：截图中的
Σn<=2*10^8、64MB 是非常极端的工程约束；下面代码给出的是正确的 Welter Function 计算与一个远优于O(n^2)的实现，用于本节模型总结。若必须严格卡截图所示最坏上限，还需要针对原题评测数据继续做 IO / 内存乃至算法工程优化，这里不把未经验证的实现冒充原题最坏界 AC。
参考代码：O(n log n + 31n) 计算 Welter Function
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
using u32=uint32_t;
u32 rev32(u32 x){x=((x>>1)&0x55555555u)|((x&0x55555555u)<<1);x=((x>>2)&0x33333333u)|((x&0x33333333u)<<2);x=((x>>4)&0x0f0f0f0fu)|((x&0x0f0f0f0fu)<<4);x=((x>>8)&0x00ff00ffu)|((x&0x00ff00ffu)<<8);return (x>>16)|(x<<16);
}
void solve(){int n;cin>>n;vector<u32>r(n);u32 base=0;for(int i=0;i<n;i++){u32 x;cin>>x;--x;base^=x;r[i]=rev32(x);}sort(r.begin(),r.end());u32 corr=0;for(int b=0;b<=30;b++){int parity=0;for(int l=0;l<n;){int rr=l+1;u32 key=b==0?0:r[l]>>(32-b);while(rr<n&&(b==0?0:r[rr]>>(32-b))==key) rr++;int cnt=rr-l;parity^=(cnt>>1)&1;l=rr;}if(parity) corr^=(1u<<b);}cout<<((base^corr)?"YES":"NO")<<endl;
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin>>T;while(T--) solve();return 0;
}
2.3 Silver Dollar Game
模型
若干硬币在一维格子上，只能向左移动，并且：
- 不能落到已有硬币上；
- 不能跨越其他硬币。
设从左到右：
与 Welter 相比，只多了“不能跨越”，但整个结构反而从二进制碰撞修正变成了非常干净的相邻配对。
结论
若 n 为偶数：
若 n 为奇数，并且格子从 0 开始：
也就是：从最右边开始两个两个配对，每对只看两枚硬币之间的空格数；若最左边剩一枚，再把它到出口的距离当成一堆。
原理
从右向左把硬币配成 (x_{n-1},x_n)、(x_{n-3},x_{n-2})……。一对中真正可自由改变的是两枚硬币之间的 gap，它恰好像一堆 Nim；左侧那枚硬币移动时虽然会改变相邻空间，却相当于把自由度传递给更左边的“缓冲部分”。按这个配对顺序做 mex，可证明每个有效 gap 独立贡献一个 Nim 堆。最值得记的是：禁止跨越带来了顺序不变，于是相邻棋子可以固定配对。
例题：POJ 1704 - Georgia and Bob
题目：https://poj.org/problem?id=1704
这是最标准的 Silver Dollar。题目位置从 1 开始，因此若 n 为奇数，最左边单独那一堆大小应为 x_1-1。
参考代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
void solve(){int n;cin>>n;vector<int>a(n);for(int&i:a) cin>>i;sort(a.begin(),a.end());int xr=0;for(int i=n-1;i>=1;i-=2) xr^=a[i]-a[i-1]-1;if(n&1) xr^=a[0]-1;cout<<(xr?"Georgia will win":"Bob will win")<<endl;
}
signed main(){ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin>>T;while(T--) solve();return 0;
}
2.4 Staircase Nim
模型
从出口向上编号 1..n，第 i 层有 a_i 个石子。一次选择第 i 层若干石子移动到第 i-1 层，第 0 层视为直接离开游戏。
结论
这里的“奇数层”本质不是输入编号奇偶，而是：
原理
定义候选值 X=a_1 xor a_3 xor ...。任意一步只在相邻两层之间搬石子，而相邻层必定一奇一偶，因此一次操作恰好改变一个参与 X 的量，所以不能保持 X 不变；另一方面，对任意 0<=Y<X，利用普通 Nim 的最高位性质，总能找到某个奇数层把它减少到合适值，使 xor 变成 Y，搬下去的石子只进入偶数缓冲层。于是所有小于 X 的值可达、X 本身不可达，mex 正好为 X。
这和 Silver Dollar 的共同直觉是：
相邻结构发生配对，其中一个量是真正的 Nim 自由度，另一个只承担缓冲 / 传递作用。
例题：LOJ 5096 / Luogu P3480 - 鹅卵石 Pebbles
题目：
https://loj.ac/p/5096
https://www.luogu.com.cn/problem/P3480
给一个非降序列：
把它差分：
若原操作让第 i 堆减少 x，差分上恰好表现成：
这就是一个出口在右边的 Staircase Nim。因此从右端开始隔一个差分 xor：
参考代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
void solve(){int n;cin>>n;vector<int>a(n+1);for(int i=1;i<=n;i++) cin>>a[i];int xr=0;for(int i=n;i>=1;i-=2) xr^=a[i]-a[i-1];cout<<(xr?"TAK":"NIE")<<endl;
}
signed main(){ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin>>T;while(T--) solve();return 0;
}
Part 3. 分裂型博弈
3.1 统一结构
这一类题的识别关键词是：
一次操作发生在中间，之后左右 / 若干块再也互相影响不到。
于是：
原局面|| 一次操作v
左子游戏 + 右子游戏 (+ ...)
如果状态只由长度 n 决定，典型递推就是：
注意：这其实就是 Multi-SG 最常见的落地形式。Part 1 讲的是抽象规则，这里讲的是最常见的“区间被切开”模型。
3.2 Kayles
Kayles 有一排 n 个瓶柱，一次可以击倒：
- 一个瓶柱；或
- 两个相邻瓶柱。
击倒中间瓶柱后，左右两段完全独立。因此：
其中分别枚举删一个和删相邻两个的位置，越界部分视作长度 0。
它真正值得记的不是一串 SG 值，而是：
经典 Kayles 的 nim-sequence 最终周期为 12（preperiod 为 71）。在竞赛中如果题目规模极大而局部规则固定，“先写分裂递推、再打表观察周期”是非常常见的路线。
3.3 Dawson's Kayles
Dawson's Kayles 可以定义为：一排棋子，每次必须拿走两个相邻棋子，剩余左右两段独立。它仍然是完全相同的 split-SG：
这个经典 octal game 0.07 的 normal-play Grundy 序列从 n=53 起进入长度为 34 的周期。这里不展开周期证明；更重要的是认识到 “删一段 -> 左右 xor -> mex -> 打表/周期” 这一整套套路。
例题：POJ 3537 - Crosses and Crosses
题目：https://poj.org/problem?id=3537
1*n 棋盘轮流放 X，谁先造出连续三个 X 谁赢。分析安全状态时，一旦在位置 i 放下 X，它左右距离不超过 2 的位置都不能再作为“不会立刻送对手胜利”的独立安全区域，于是剩余可继续博弈的部分被切成：
因此：
参考代码
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N=2005;
int sg[N];
int dfs(int n){if(sg[n]!=-1) return sg[n];bool vis[N]={0};for(int i=1;i<=n;i++){int l=max(0,i-3),r=max(0,n-i-2);vis[dfs(l)^dfs(r)]=1;}int g=0;while(vis[g]) g++;return sg[n]=g;
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);memset(sg,-1,sizeof(sg));sg[0]=0;int n;cin>>n;cout<<(dfs(n)?1:2)<<endl;return 0;
}
例题：2025 CCPC Online F - 连线博弈
题目：https://qoj.ac/contest/2534/problem/14552
这题很适合放在 Kayles 后面，因为它把“分裂 SG”包装得更深了一层。
先看一个连通块。若其中有 x 个当前可用点，一次连线会消耗两个点，并把剩余点分成两个互不影响的子块，所以：
打表后可发现从足够大的位置开始周期为 34，实现中预处理到 1000，对 x>500 使用：
真正麻烦的是“哪些点属于同一连通块”。对每条已有线段，给线段内部点集 xor 一个随机 A，给线段外部点集 xor 一个随机 B；两个未占用点若对所有线段都处于完全相同的相对区域，最终 Hash 就相同，可以视作同一个连通块。区间 xor 用差分事件离线维护，最后统计每个 Hash 对应多少自由点，再 xor 各块 SG。这里使用 64 位随机 Hash，属于概率正确算法，碰撞概率可以忽略。
参考代码
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
using ull=unsigned long long;
const int K=1005;
int sg[K];
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
void init(){sg[0]=sg[1]=0;for(int x=2;x<=1000;x++){bool vis[K]={0};for(int a=0;a<=x-2;a++) vis[sg[a]^sg[x-2-a]]=1;int g=0;while(vis[g]) g++;sg[x]=g;}
}
int getsg(int x){if(x<=500) return sg[x];return sg[(x-500)%34+500];
}
void add(map<int,ull>&d,int l,int r,ull v){if(l>r) return;d[l]^=v;d[r+1]^=v;
}
void solve(){int n,m;cin>>n>>m;if(m==0){cout<<(getsg(n)?"YES":"NO")<<endl;return;}map<int,ull>d;vector<int>ed;for(int i=1;i<=m;i++){int x,y;cin>>x>>y;++x;++y;if(x>y) swap(x,y);ed.push_back(x);ed.push_back(y);ull A=rng(),B=rng();add(d,x+1,y-1,A);add(d,1,x-1,B);add(d,y+1,n,B);}sort(ed.begin(),ed.end());ed.erase(unique(ed.begin(),ed.end()),ed.end());d[n+1]^=0;map<ull,int>cnt;int last=1;ull cur=0;for(auto [pos,val]:d){if(last<=pos-1){int occ=upper_bound(ed.begin(),ed.end(),pos-1)-lower_bound(ed.begin(),ed.end(),last);cnt[cur]+=pos-last-occ;}cur^=val;last=pos;}int ans=0;for(auto [h,c]:cnt) ans^=getsg(c);cout<<(ans?"YES":"NO")<<endl;
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);init();int T;cin>>T;while(T--) solve();return 0;
}
这题有两个很值得留下的坑：第一，不能看见线段就想当然认为每条线段对应一个独立子游戏，真正独立的是连通块；第二，SG 周期只是解决了“一个块有多少点”，划分块本身还需要另一套 Hash 技巧。
Part 4. 数学结构型博弈
这类题仍然是公平组合博弈，但答案不再表现为“把几个显然独立的量 xor 一下”，而是出现 Beatty 序列、黄金分割、特殊 P-position 构造等数学结构。
4.1 Wythoff Nim
模型
两堆石子 a<=b，一次可以：
- 只减少第一堆；
- 只减少第二堆；
- 两堆同时减少相同的正整数。
结论
令：
所有 P-position 恰好是：
又因为：
所以：
于是给定 a<=b，设：
只需判断：
原理
两列 Beatty 序列 floor(k*phi) 与 floor(k*phi^2) 恰好把所有正整数不重不漏地划分掉。不同 P-position 的差值 k 不同，因此不能通过“两堆同减”互达；Beatty 序列的互补性又保证不能通过只减一堆从一个 P-position 到另一个 P-position。反过来，每个非 P-position 都能通过只减一堆或同减两堆落到唯一合适的 P-position。于是满足“P 不到 P、N 必到 P”的标准刻画。
例题：POJ 1067 - 取石子游戏
题目：https://poj.org/problem?id=1067
标准 Wythoff，直接按差值 k=b-a 判断黄金分割下取整即可。
参考代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
signed main(){ios::sync_with_stdio(false);cin.tie(nullptr);int a,b;cin>>a>>b;if(a>b) swap(a,b);int k=b-a;long double phi=(1.0L+sqrtl(5.0L))/2.0L;int x=(int)floorl(k*phi);cout<<(a==x?0:1)<<endl;return 0;
}
若数据被放大到接近
1e18甚至更高，不要无脑依赖浮点取整；这时应考虑高精度或等价整数判定。经典 POJ 数据范围使用long double足够。
4.2 同步减法类：Take Apples
例题：Nowcoder NC26003 - Take Apples
题目：https://ac.nowcoder.com/acm/problem/26003
初始三堆苹果为：
一次可以：
- 选一堆拿
1..S个； - 三堆同时拿相同的正数，且这个数可以大于
S。
最后拿完者胜。
针对题目规定的这个对称初态，结论非常简洁：
当 N<=S 时，两堆相同的 N 可以用对称应对理解：若对手只动其中一堆，就在另一堆做同样操作；第一堆 M 则出现经典“每两步合计拿 S+1”的模结构。对三堆同步操作再配合第一堆补到 S+1，可以维持这个标准败态。若 M mod(S+1)!=0，先手直接修正第一堆即可。N>S 的区域则都属于先手必胜，完整证明需要对后继分类讨论；这题更适合把上述条件当作特定 (M,N,N) 初态的结论记忆，而不要误写成任意三堆游戏的完整 P-position 分类。
参考代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
signed main(){ios::sync_with_stdio(false);cin.tie(nullptr);int S,M,N;while(cin>>S>>M>>N){if(N<=S&&M%(S+1)==0) cout<<"Bob"<<endl;else cout<<"Alice"<<endl;}return 0;
}
它和 Wythoff 的共同点是“允许同步减少多个堆”，但结论并不是黄金分割，所以更适合单独归到“同步减法类”，而不是强行叫作 Wythoff 变形。
Part 5. 结构性胜负与策略窃取
5.1 不要见到博弈就硬算 SG
SG 很强，但竞赛里还有一类题，真正要求的只是：
如果题目：
- 状态巨大，根本不像有限小状态 DP；
- 操作之间高度耦合，很难拆成游戏和；
- 只问谁赢，不要求 winning move；
- 存在明显对称、偏序、最小/最大“无害操作”；
那么应该优先尝试：
- 配对策略；
- 对称策略；
- 不变量；
- P/N 状态直接构造；
- Strategy Stealing（策略窃取）。
SG 是工具，不是博弈题的唯一入口。
5.2 Chomp 与 Strategy Stealing
经典 Chomp：https://cariboutests.com/games/chomp.php?lang=cn
有一个 n*m 矩形点阵 / 巧克力，每次选择仍存在的一个位置，并删除它及其右下方的所有位置；左上角是毒点，谁取到毒点谁输。
结论
除了只有一个毒点的 1*1 棋盘：
注意这里是“存在”，经典 Strategy Stealing 一般并不会告诉你具体第一步应该下在哪里。
最精髓的策略窃取证明
假设某个非平凡矩形是先手必败。先手先吃掉最右下角那个安全格，它只删除自己。若此后局面对后手是必胜的，设后手存在某个获胜第一步 x；但 x 的删除区域必然也包含刚才那个最右下角格，于是原来的先手完全可以一开始就直接走 x，得到与“先吃右下角、再由对手走 x”相同的剩余局面，却把行动权交换给了对手，矛盾。因此原局面不可能是必败态。
结论判定代码（若题目只问胜负）
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
signed main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n,m;cin>>n>>m;cout<<(n==1&&m==1?"Bob":"Alice")<<endl;return 0;
}
Chomp 很适合提醒自己：能证明先手必胜，不代表能高效构造具体必胜着。 这和 SG 算出非零后通常还能进一步找
SG=0后继的情况很不一样。
5.3 因子偏序上的高维 Chomp
拓展题：给定正整数 n。双方轮流选择一个还可以拿的因子 d，拿走 d 后，d 的所有因子都不能再拿；谁拿到 n 谁输。
把：
的任意因子写成：
于是每个因子就是一个高维格点：
而：
因此整个因子集合就是若干条链的直积偏序，选 d 后删除它的所有因子，就是高维 Chomp 的一个方向版本；n 对应最高角，是毒点。
结论
证明直接复制策略窃取：1 是最小安全元素，先拿 1 只会删掉自己。若之后 Bob 有某个获胜回应 d，由于 1|d，Alice 原本就可以第一步直接拿 d，得到完全相同的剩余局面并交换行动权，矛盾。
参考代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
signed main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin>>n;cout<<(n==1?"Bob":"Alice")<<endl;return 0;
}
这道题最漂亮的点不是代码，而是：因数关系 -> 质因数指数向量 -> 逐维偏序 -> 高维 Chomp。
5.4 Independent Nim：一个“不能拆成独立子游戏”的反例
题目：AtCoder ARC225 B - Independent Nim
给一个 01 串。一次可以选择若干个当前为 1 的位置改成 0，但同一次选中的位置两两不能相邻；无法操作者输。
最容易犯的错
看到：
111 0 11111 0 11
很容易把每个连续 1 段当成独立子游戏，然后 xor 每段 SG。
这是错的，因为同一回合允许同时从多个连续段各删一些位置。一步操作可以同时作用于多个“段”，所以这些段根本不是 disjunctive sum，普通 SG xor 前提不成立。
P-position 结论
全 0 也满足这个条件，因此同样是 Bob 胜。
原理
把“所有 1 段都是 11”叫标准形。标准形中一次合法操作在每个 11 中最多删一个，因此只要操作就必然破坏至少一对 11，走到非标准形；反过来，对任意长度不为 2 的连续段，都能按周期结构留下若干个 11，删除位置之间至少隔两个 1，所以所有非标准段可以在同一回合一起整理成标准形。于是标准形的任何后继都是 N-position，而任何非标准形都有一步走到标准形。
一个方便记的构造是：长度 L 的段可以留下：
L = 3k : (110)^k
L = 3k + 1 : 0(110)^k
L = 3k + 2 : (110)^k11
其中 0 表示这一回合删除的位置。所有被删位置两两不相邻。
参考代码
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
void solve(){int n;cin>>n;bool ok=1;int cnt=0,x=0;for(int i=1;i<=n;i++){cin>>x;if(x) cnt++;else{if(cnt&&cnt!=2) ok=0;cnt=0;}}if(cnt&&cnt!=2) ok=0;cout<<(ok?"Bob":"Alice")<<endl;
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin>>T;while(T--) solve();return 0;
}
这题非常适合作为全文最后的反例：
判断能否 xor，永远要回到定义：一次是否只能操作一个子游戏？一个子游戏的操作是否完全不影响另一个？
最后：模型识别速查表
| 题面特征 | 第一反应 | 核心结论 / 工具 |
|---|---|---|
| 普通有限无偏博弈，小状态 | SG 打表 | mex |
| 多个完全独立部分，一次只能动一个 | 游戏和 | 子 SG xor |
| 最后一步输 | Anti-SG / Misère | 先检查是否满足 SJ 条件；Misère Nim 单独记 |
| DAG 上棋子沿边走 | DAG SG | sg[u]=mex(sg[v]) |
| 树根删边，断开部分消失 | Green Hackenbush 树 | sg[u]=xor(sg[v]+1) |
| 一步把一个状态裂成多个独立状态 | Multi-SG | 后继 nimber 先 xor，再 mex |
| 每回合所有未结束子游戏都必须动 | Every-SG | 最大 step 奇偶 |
| 棋子任意向左，可跨越、可重合 | Nimble | 所有位置 xor |
| 可跨越但不能重合 | Welter | Welter Function / v2(ai-aj) |
| 不能跨越也不能重合 | Silver Dollar | 从右向左相邻配对，gap xor |
| 石子只能逐层向出口移动 | Staircase Nim | 距出口奇数层 xor |
| 一步删除局部后左右独立 | Kayles / split game | mex(sg[L]^sg[R]) |
一维固定局部规则、n 巨大 |
SG 周期 | 打表 + 验证周期 |
| 两堆可单减或同步等量减 | Wythoff | 黄金分割 / Beatty 序列 |
| 规则有同步操作但不完全是 Wythoff | 特殊 P-position | 不要强行套黄金分割 |
| 矩形 / 偏序中选点删除一个方向区域 | Chomp | Strategy Stealing |
| 看似分成多段，但一步能同时动多段 | 不能直接 xor | 先重新检查“独立子游戏”前提 |
最后真正该记的几条
- SG 不是胜负分数，而是 Nim 等价类。
- mex 真正表达的是：所有小值可达，自己不可达。
- xor 的前提不是“有多个部分”，而是这些部分构成 disjunctive sum。
- 一个操作产生多个独立部分：先 xor 新部分，再对所有操作做 mex。
- 规则只改一点，模型可能彻底改变：Nimble -> Welter -> Silver Dollar 就是最典型的例子。
- 打表不是不会做时的最后手段，而是猜 SG 闭式、周期、P-position 的第一实验工具。
- 不是所有博弈都值得求完整 SG。只问胜负时，配对、不变量、P/N 构造、策略窃取可能更直接。
参考资料
- 贾志豪：《组合游戏略述——浅谈 SG 游戏的若干拓展及变形》
GitHub PDF 镜像 - C. P. Welter, The theory of a class of games on a sequence of squares, in terms of the advancing operation in a special group
DOI - Tomoaki Abuku, Transfinite Version of Welter's Game
arXiv - Yuki Irie, p-Saturations of Welter's Game and the Irreducible Representations of Symmetric Groups
arXiv - Yuki Irie, A p-calm game and Welter's game
arXiv - Aaron N. Siegel, Misère Games and Misère Quotients（其中也整理了 Kayles / Dawson's Kayles 的 normal-play 周期结论）
arXiv PDF