公平组合博弈建模

公平组合博弈的 P/N 状态、Nim 定理、SG 函数与 Sprague-Grundy 定理详见 公平组合博弈理论。

理论解决的是：当一个游戏已经完成建模以后，怎样递推胜负、怎样组合独立子游戏。但真正做题时，更困难的问题往往发生在这之前。

一、当前局面到底需要保存什么？

最直接的想法是把“当前局面”作为状态，然后按照 P/N 规则递推。

但题面给出的全部信息未必都需要进入状态。真正应该保存的是：所有会影响未来合法操作与最终胜负的信息。

Q1

P2953 Cow Digit Game S
当前整数每次可以减去最大数码或最小非零数码，数字变成 $0$ 后无法操作的一方失败。

数据规模：$N_i\le10^6$。

当前整数 $x$ 已经完整决定了下一步所有合法操作，过去经历了怎样的操作并不会再影响未来。因此状态只需要保存 $x$。

同时，每次操作后 $x$ 严格减小，状态图天然无环，令 win[x] 表示当前玩家面对 $x$ 时能否获胜，只要后继中存在一个必败态，当前就是必胜态；若所有后继都必胜，当前就是必败态。

注：本题发现博弈胜负 DP 与普通 DAG DP 其实没有本质区别。

Q2

P1288 取数游戏 II
在一个带权环上从固定节点出发。每次选择硬币相邻的一条非零边，将其权值减小，并把硬币移动到这条边的另一端；无法继续移动的一方失败。判断先手是否存在必胜策略。

数据规模：$n\le20$。

如果直接按照题面描述状态，需要记录整个环、所有边权以及硬币位置，状态显然过于复杂。

继续分析操作会发现：一旦某个方向上遇到权值为 $0$ 的边，硬币以后就永远无法跨过它。

因此从初始位置出发，真正可能影响未来的只有起点两侧、直到最近零边为止的连续非零部分。零边之外的整个环虽然仍然存在于输入中，但已经不可能再次影响任何合法操作。

设起点两侧到最近零边前的连续非零边数为 $l,r$。若经过一条边后没有将其清零，对手可以立即折返并清零，因此游戏最终只与所选方向的长度奇偶有关：$l,r$ 中至少一个为奇数时先手胜，否则后手胜。

注：本题的关键在于理解状态压缩，被删掉的信息是因为它不会影响后续的合法转移。

Q3

P4018 Roy&October 之取石子
有 $n$ 个石子，每次只能取走 $p^k$ 个石子，其中 $p$ 为质数、$k$ 为非负整数，并且不能超过当前剩余石子数，取走最后一个石子的人获胜。

数据规模：$1\le n\le5\times10^7$。

这里当前剩余石子数 $n$ 已经是充分状态，和 Q1 没有本质区别，P/N 转移也很好写。问题只在于状态规模已经太大，不适合逐个递推。

既然最终只关心当前状态是不是 P，就可以反过来问：能不能不计算所有状态，而是直接描述整个 P 状态集合？

小规模打表后，我们发现 $6$ 的倍数恰好是 P 状态，但猜测不等于证明，仍然需要验证 P 集合的两条性质。

1. P 状态能否一步到另一个 P 状态：不能。两个 $6$ 的倍数之差仍是正的 $6$ 的倍数，同时含有质因子 $2$ 和 $3$，不可能是只含一种质因子的质数幂。

2. 任意非 P 状态能否一步到某个 P 状态：能。若 $n\bmod 6=r\in\{1,2,3,4,5\}$，分别取走 $1,2,3,4,5$ 个石子即可；其中 $1=p^0$，$2,3,5$ 是质数，$4=2^2$，均为合法操作。

得证，P 状态集合就是 $6$ 的倍数。

---

摘要

如果原状态已经足够，可以直接递推；如果题目信息过多，就删除以后不会影响合法转移的信息；如果状态数量过多，则可以尝试直接刻画 P 状态集合。

二、局面有很多部分，就真的可以分别处理吗？

当题目中出现很多石子堆、很多行或者很多区域时，很容易想到把它们拆成若干子游戏，再利用 Nim 或 SG 定理组合。

但在异或之前，首先需要确认：这些部分是否真的互不影响？游戏的终止规则是否仍然满足标准模型？

标准 Nim 作为最基本的独立组合模型不再展开，具体证明与必胜策略见 公平组合博弈理论。

Q4

P4279 小约翰的游戏
有 $N$ 堆石子，两人轮流操作，每次仍然可以选择任意一堆并取走任意正数颗石子，但本题规定取走最后一颗石子的人失败。John 先手，双方均采用最优策略，判断 John 是否获胜。

数据规模：$T\le500$，$N\le50$。

本题的中间操作与标准 Nim 完全相同，但最后一步的胜负规则改变了。而终止规则会从终局开始反向改变整个 P/N 结构，因此不能只因为“操作和 Nim 一样”就直接套用 Nim 定理。

先考虑所有堆都只有 $1$ 的情况，每一步都只能完整拿走一堆，那问题就退化为堆数的奇偶问题。若至少存在一堆大于 $1$，胜负判定仍然与普通 Nim 相同：总异或为 $0$ 时为 P，否则为 N。为什么？

证明仍然可以验证 P 集合：总异或为 $0$ 且存在大堆时，修改任意一堆都会使异或变为非零，并且不可能一步进入“奇数个 $1$”的另一类 P 状态；

反过来，总异或非零时，如果至少有两堆大于 $1$，可以按普通 Nim 构造把异或变为 $0$，如果只剩一堆大于 $1$，则直接将它变为 $0$ 或 $1$，使最终留下奇数个 $1$。

Q5

P3480 KAM-Pebbles
有 $n$ 堆石子，始终满足 $a_1\le a_2\le\cdots\le a_n$。每次选择一堆减少若干石子，但操作以后仍必须保持非降；无法进行合法操作的一方失败。

数据规模：$n\le1000$。

本题不能直接把每个 $a_i$ 看成一个 Nim 堆。

因为第 $i$ 堆能够减少多少，不只取决于 $a_i$ 本身，还受到 $a_{i-1}$ 的限制，所以这些堆并不真正独立。

那能不能换一种表示，把原来的相邻约束局部化？

那在这种情况下，如何把原游戏转化为相对独立的游戏呢？

定义差分 $b_i=a_i-a_{i-1}$，其中 $a_0=0$。由于 $a_{i-1}\le a_i\iff b_i\ge0$，原来的大小约束被转化成了差分的非负性。

但差分以后还不能直接把每个 $b_i$ 看成独立的 Nim 堆。若将 $a_i$ 减少 $d$，则差分发生 $b_{i} \gets b_{i} - d$，$b_{i+1} \gets b_{i+1} + d$，其中 $1 \le d \le b_{i}$，若 $i = n$，则只有 $b_{n} \gets b_{n} - d$。

因此一次操作相当于把 $b_{i}$ 中的任意正数个石子向后一层移动，直到从第 $n$ 层离开游戏，这也是这种 “阶梯 Nim” 的结构。

接着从出口隔层取差分，定义：$X = b_{n} \oplus b_{n-2} \oplus \dots$。仍然可以按照 P 状态的两条条件证明：

1. 若 $X=0$，任意一次操作都会恰好改变上述异或中的一个 $b_i$：操作被选中的位置时该项减小，操作未被选中的位置时下一项增加，因此新的异或一定非零。

2. 若 $X\ne0$，按照普通 Nim 的构造，一定可以选择某个参与异或的 $b_i$，将其减小为 $b_i'=b_i\oplus X<b_i$。在原游戏中把 $a_i$ 减少 $b_i-b_i'$ 即可；虽然同时会增加 $b_{i+1}$，但 $b_{i+1}$ 不参与异或，因此能够恰好把 $X$ 变成 $0$。

所以隔层异或后的差分数组，刚好就是本题的 P 状态。

三、P/N 不够以后，一个子游戏到底是什么？

只知道每个子游戏是 P 还是 N，并不能决定它们组合以后的胜负，这也是引入 SG 函数的原因。

但落实到具体题目时，SG 的定义并不会自动告诉我们：一个子游戏应该怎样定义状态？整个游戏应该先怎样拆，再怎样压缩？

Q6

Typical90 031 - VS AtCoder
有 $N$ 堆石子，第 $i$ 堆包含 $W_i$ 个白石和 $B_i$ 个蓝石。每次选择一堆 $(w,b)$，进行以下一种操作：

• 若 $w\ge1$，移走一个白石，同时加入 $w$ 个蓝石，即 $(w,b)\to(w-1,b+w)$；
• 若 $b\ge2$，选择 $1\le k\le\lfloor b/2\rfloor$，移走 $k$ 个蓝石，即 $(w,b)\to(w,b-k)$。

无法进行任何操作的一方失败。你可以选择先手或后手，判断为了保证获胜应该选择哪一方。

数据规模：$1\le N\le10^5$，$0\le W_i,B_i\le50$，且 $(W_i,B_i)\neq(0,0)$。

如果只保存一堆石子的总数量，未来操作无法确定，因为白石和蓝石拥有完全不同的转移规则。所以单个子游戏最自然的状态就是 $(w,b)$。

合法转移有两类：$(w,b)\to(w-1,b+w)$，或者 $(w,b)\to(w,b-k)$，其中 $1\le k\le\lfloor b/2\rfloor$。

状态确定以后，在记忆化搜索之前还需要确认状态图是否无环。第一种操作虽然会增加 $b$，但一定减少 $w$；第二种操作保持 $w$ 不变，但一定减少 $b$。因此按照 $(w,b)$ 的字典序观察，每一步都严格下降。

接着发现状态规模并不是夸张到无法枚举的，所以我们可以直接打完表，然后输出答案。虽然初始范围只有 $w,b\le 50$，但白石操作会增加蓝石；从 $w=50$ 一路操作到 $0$，蓝石最多增加 $50 + 49 + \cdots + 1 = 1275$。

加上初始的 $50$ 个蓝石，可达上界为 $1325$，因此 SG 数组要开大一点。

▶

Typical90 031

int sg[55][1505];
int dfs( int w, int b ) {
    if( sg[w][b] != -1 ) return sg[w][b];
    set<int> s;
    if( w >= 1 ) s.insert( dfs( w - 1, b + w ) );
    for( int k = 1; k <= b / 2; ++ k ) {
        s.insert( dfs( w, b - k ) );
    }
    sg[w][b] = 0;
    while( s.count( sg[w][b] ) ) sg[w][b] ++;
    return sg[w][b];
}

int w[maxn], b[maxn];
void solve( ) {
    int n = read( );
    for( int i = 1; i <= n; ++ i ) w[i] = read( );
    for( int i = 1; i <= n; ++ i ) b[i] = read( );
    memset( sg, -1, sizeof sg );
    ll Xsum = 0;
    for( int i = 1; i <= n; ++ i ) {
        Xsum ^= dfs( w[i], b[i] );
    }
    if( Xsum ) cout << "First" << '\n';
    else cout << "Second" << '\n';
}

Q7

P2575 高手过招
棋盘有若干行，每一行长度为 $20$，每颗棋子只能移动到同一行右侧的第一个空位。两人轮流移动一颗棋子，无法继续移动的一方失败。

数据规模：$n \le 1000$。

显然不能直接把整张棋盘作为一个 SG 状态。但一次操作只会改变某一行，并且某一行发生变化以后，不会影响其他行有哪些合法移动。因此整张棋盘天然可以拆成 $G = G_{1} + G_{2} + \dots + G_{n}$。

其中每一行就是一个独立子游戏，于是我们就可以拆成类似 Nim 游戏的子游戏。而一行只有 20 个位置，所以我们可以用一个 20 位的 bitmask 来状态压缩。

对于每个单行状态，枚举每颗棋子移动到右侧第一个空位产生的后继，求 mex 得到单行 SG，最终将所有行异或即可。

▶

P2575

int sg[maxn];
int dfs( int cur ) {
    if( sg[cur] != -1 ) return sg[cur];
    set<int> s;
    for( int j = 0; j < 20; ++ j ) {
        if( !( cur & (1 << j) ) ) continue;
        int k = j + 1;
        while( k < 20 && ( cur & (1 << k) ) ) ++ k;
        if( k == 20 ) continue;
        int nxt = cur ^ ( 1 << j ) ^ ( 1 << k );
        s.insert( dfs( nxt ) );
    }
    sg[cur] = 0;
    while( s.count( sg[cur] ) ) sg[cur] ++;
    return sg[cur];
}

void solve( ) {
    int n = read( );
    ll Xsum = 0;
    for( int i = 1; i <= n; ++ i ) {
        int m = read( );
        int mask = 0;
        for( int j = 1; j <= m; ++ j ) {
            int p = read( );
            mask |= (1 << (p - 1));
        }
        Xsum ^= dfs( mask );
    }
    if( Xsum ) cout << "YES" << '\n';
    else cout << "NO" << '\n';
}

sg 数组应当在处理所有测试数据之前统一初始化为 -1，让不同测试复用已经求出的单行状态。

Q8

P8369 条纹
给定长度分别为 $c,z,n$ 的三种条纹，每种条纹数量无限。对于一个长度为 $p$ 的一维棋盘，两名玩家轮流选择一种条纹放到棋盘上，要求条纹不能伸出棋盘、不能与已有条纹重叠，并且必须沿方格边界放置。无法继续放置条纹的一方失败。

给定多个棋盘长度 $p$，分别判断每个棋盘上先手是否存在必胜策略。

数据规模：$1\le c,z,n,m,p\le1000$，其中 $m$ 为询问的棋盘数量。

这道题很容易把 SG 中的两种运算混在一起。

当前状态只是一个长度为 $m$ 的完整空白区间。但选择某个位置放下一条长度为 len 的条纹后，剩余空间会被切成了两段，左侧长度为 $l$ 的区间，以及右侧长度为 $r = m - l - len$ 的区间。

这两个区间是互不影响的，所以这一次操作得到的后继状态实际上是两个独立游戏的和，其 SG 为 $SG(l) \oplus SG(r)$。

But，当前玩家有很多种不同的放置方式，而这些不同的放置方式不是同时存在的独立游戏，而是当前玩家可以选择的不同后继，此时取 $SG(m) = \operatorname{mex}\{ SG(l) \oplus SG(m-l-len) \}$。

注：同一个后继内部同时存在的独立子游戏，先 XOR；当前状态不同合法操作产生的后继，再 mex。

四、SG 递推已经正确，为什么复杂度还是不够？

到了这里，状态定义和 SG 递推本身通常已经没有问题。但“能写出正确 SG”并不意味着“能够在数据范围内计算”。

这时候首先应该判断瓶颈究竟来自哪里：

1. 状态数量本身太大：无法逐状态计算，需要寻找周期、位结构或者闭式；

2. 状态数量可以接受，但枚举后继太慢：保留原 SG 递推，优化状态图建边；

3. 状态和转移都很复杂：先构造小规模正确暴力，再从真值中寻找新的表示。

Q9

ABC297 G - Constrained Nim 2
有 $N$ 堆石子，第 $i$ 堆初始有 $A_i$ 颗。两人轮流操作，每次选择一堆，并从中取走 $L$ 到 $R$ 颗石子；只有剩余石子足够时才能进行对应操作。无法进行任何操作的一方失败，判断先手还是后手在最优策略下获胜。

数据规模：$1\le N\le2\times10^5$，$1\le L\le R\le10^9$，$1\le A_i\le10^9$。

单堆 SG 可以直接写成 $SG(x)=\operatorname{mex}\{SG(x-L),\dots,SG(x-R)\}$，但很难处理 $1e9$ 的数据规模。

(1, 1): 0 1 0 1 0 1 0 1 0 1
(1, 2): 0 1 2 0 1 2 0 1 2 0
(1, 3): 0 1 2 3 0 1 2 3 0 1
(1, 4): 0 1 2 3 4 0 1 2 3 4
(1, 5): 0 1 2 3 4 5 0 1 2 3
(1, 6): 0 1 2 3 4 5 6 0 1 2
(1, 7): 0 1 2 3 4 5 6 7 0 1
(1, 8): 0 1 2 3 4 5 6 7 8 0
(1, 9): 0 1 2 3 4 5 6 7 8 9
(1, 10): 0 1 2 3 4 5 6 7 8 9 10 0

从表中猜测周期为 $L+R$，并得到 $\displaystyle SG(x)=\left\lfloor\frac{x\bmod(L+R)}L\right\rfloor$。

可以按周期验证 mex。设 $T=L+R$、$r=x\bmod T$、$q=\lfloor r/L\rfloor$。取走 $[L,R]$ 颗石子后，后继不会仍落在编号为 $q$ 的块中；而对任意 $t<q$，都能选择一个合法取法落入编号为 $t$ 的块。因此后继 SG 包含 $0,1,\dots,q-1$ 而不包含 $q$，其 mex 正是 $q$。

▶

ABC297G

void solve( ) {
    int n = read( );
    int L = read( ), R = read( );
    ll Xsum = 0;
    for( int i = 1; i <= n; ++ i ) {
        int ai = read( );
        int sg = ( ai % ( L + R ) ) / L;
        Xsum ^= sg;
    }
    if( Xsum ) cout << "First" << '\n';
    else cout << "Second" << '\n';
}

Q10

ABC368 F - Dividing Game
给定 $N$ 个整数 $A_1,A_2,\dots,A_N$。两人轮流操作，每次选择一个 $A_i$，再选择它的一个不等于自身的正因子 $x$，并将 $A_i$ 替换为 $x$。无法进行操作的一方失败。Anna 先手，双方均采用最优策略，判断最终谁获胜。

数据规模：$1\le N\le10^5$，$2\le A_i\le10^5$。

每个 $A_i$ 之间互不影响，所以可以把每个整数看成一个独立子游戏，分别求出 $SG(A_i)$ 后全部异或。

对于单个整数 $x$，合法后继就是它的所有真因子，因此可以直接按照定义写出：$SG(x) = \operatorname{mex} \{SG(d)\mid d\mid x,\ d<x\}$。

最直接的实现是对每个状态 $x$ 枚举所有 $1\le d<x$，判断 $d\mid x$。SG 本身没有问题，但这样相当于对大量整数反复进行整除判断，复杂度接近平方级，无法通过。

▶

ABC368F TLE

int sg[maxn];
int dfs( int x ) {
    if( sg[x] != -1 ) return sg[x];
    set<int> s;
    for( int y = 1; y < x; ++ y ) {
        if( x % y != 0 ) continue;
        s.insert( dfs( y ) );
    }
    sg[x] = 0;
    while( s.count( sg[x] ) ) sg[x] ++;
    return sg[x];
}

void solve( ) {
    int n = read( );
    ll Xsum = 0;
    memset( sg, -1, sizeof sg );
    sg[0] = sg[1] = 0;
    for( int i = 1; i <= n; ++ i ) {
        int ai = read( );
        int g = dfs( ai );
        Xsum ^= g;
    }
    if( Xsum ) cout << "Anna" << '\n';
    else cout << "Bruno" << '\n';
}

这里真正的瓶颈不是“状态太多”，而是每个状态都重新寻找它的所有后继。因子关系形成的状态图与具体输入无关，可以提前一次性构造；这样 divs[x] 就保存了 $x$ 的所有真因子，之后继续按照原来的 SG 定义递推即可。

▶

ABC368F

vector<int> divs[maxn];
void init( int N ) {
    for( int i = 1; i <= N; ++ i ) {
        for( int j = 2; j * i <= N; ++ j ) {
            divs[j * i].push_back( i );
        }
    }
}

int sg[maxn];
int dfs( int x ) {
    if( sg[x] != -1 ) return sg[x];
    set<int> s;
    for( int y : divs[x] ) {
        s.insert( dfs( y ) );
    }
    sg[x] = 0;
    while( s.count( sg[x] ) ) sg[x] ++;
    return sg[x];
}

void solve( ) {
    int n = read( );
    ll Xsum = 0;
    memset( sg, -1, sizeof sg );
    sg[0] = sg[1] = 0;
    for( int i = 1; i <= n; ++ i ) {
        int ai = read( );
        int SG = dfs( ai );
        Xsum ^= SG;
    }
    if( Xsum ) cout << "Anna" << '\n';
    else cout << "Bruno" << '\n';
}

进一步的 SG 结构

事实上还可以证明 $SG(x)=\Omega(x)$，其中 $\Omega(x)$ 表示质因子个数并计重数。

这能够把状态图 SG 进一步压缩成质因数分解问题，但不是本章节需要扩展的内容，略。

Q11

P2148 E&D
有偶数个石子堆，相邻两堆 $(1,2),(3,4),\dots$ 分别组成一组。一次操作选择其中一组：先移走组内的一整堆，再将同组的另一堆拆成两个非空石子堆，分别放回这一组的两个位置。

两人轮流操作；当所有石子堆都只有 $1$ 颗石子时，不存在合法操作，当前玩家失败。小 E 先手，判断是否存在必胜策略。

数据规模：$1\le T\le20$，$1\le N\le2\times10^4$ 且 $N$ 为偶数，$1\le S_i\le2\times10^9$。

每一组之间互不影响，所以可以把每对 $(S_{2i-1},S_{2i})$ 看成一个独立子游戏，分别求出 SG 后全部异或。

对于一组 $(x,y)$，可以移走其中一堆，再把另一堆任意拆成两个非空部分，所以合法后继包括所有：$(k, x - k), 1 \le k < x$；$(k, y - k), 1 \le k < y$。

于是可以先按照定义打出小范围二维 SG 表。

▶

P2148-BF

int sg[55][55];

int dfs( int x, int y ) {
    if( sg[x][y] != -1 ) return sg[x][y];
    set<int> s;
    for( int k = 1; k < x; ++ k ) {
        s.insert( dfs( k, x - k ) );
    }
    for( int k = 1; k < y; ++ k ) {
        s.insert( dfs( k, y - k ) );
    }
    sg[x][y] = 0;
    while( s.count( sg[x][y] ) ) sg[x][y] ++;
    return sg[x][y];
}

直接观察完整二维表很难看出结构，于是先固定 $x=1$。此时得到 $SG(1,y)=0,1,0,2,0,1,0,3,\dots$，恰好等于 $y$ 二进制末尾连续 $0$ 的数量，也就是 $v_2(y)$。

但继续观察 $x=2$ 后，这个规律失效，说明真正的结构同时依赖 $x,y$。于是改变观察对象，从 $(x,y)$ 转向 $(x-1,y-1)$，最终发现只需要关注 $z=(x-1)\mathbin{|}(y-1)$，其 SG 恰好等于 $z$ 末尾连续 $1$ 的数量，而末尾连续 $1$ 的数量可以通过取反后统计末尾 $0$ 实现。

▶

P2148-AC

void solve( ) {
    int n = read( );
    ll Xsum = 0;
    for( int i = 1; i <= n / 2; ++ i ) {
        int x = read( ), y = read( );
        int z = (x - 1) | (y - 1);
        int SG = __builtin_ctz( ~z );
        Xsum ^= SG;
    }
    if( Xsum ) cout << "YES" << '\n';
    else cout << "NO" << '\n';
}

五、小结

这一轮公平组合博弈的建模过程，本质上是在不断压缩“为了决定胜负真正需要的信息”。

首先是状态。

如果题面状态已经能够完整描述未来，直接做 P/N 递推即可；如果题面信息过多，就删除以后不会影响合法操作的信息；如果状态数量过多，则可以进一步从逐状态递推转向直接描述 P 集合。

接着是独立性。

题面中看起来分开的几个部分，不一定真的可以分别求解。需要检查一次操作是否只影响其中一个部分，以及它是否会改变其他部分未来的合法操作。同时，终止规则也是游戏模型的一部分。若原变量之间存在约束，还可以尝试通过差分等方式改变表示，重新暴露局部自由度。

当 P/N 无法保存组合信息以后，才进入 SG。

此时需要继续解决：一个子游戏应该保存什么状态、怎样证明状态图无环、真实可达范围是多少、整个局面应该怎样拆分。若一次操作会产生多个独立区域，还要严格区分：

同一个后继内部的独立子游戏取 XOR；不同合法操作产生的后继取 mex。

最后，即使 SG 递推已经正确，复杂度仍可能不够。

这时需要进一步判断瓶颈：

• 状态太多：寻找周期、闭式或新的表示；

• 后继太多：优化状态图的构造；

• 原表示难以观察：保留正确暴力，改变坐标或表示继续寻找结构。

所以 SG 本身并不是博弈题的终点。