SG 函数学习笔记：从入门到黑题

XYstarabyss · 2025-05-27 16:59:52 · 题解

写这篇题解来复习一下 SG 函数。

简化题意：给定 N 堆石子，一次操作指定一堆数量不小于 F 的石子（假设石子数量为 X），分成 M （2 \le M）堆数量为 \lfloor \dfrac{X}{M} \rfloor 或 \lfloor \dfrac{X}{M} \rfloor + 1 堆石子（全部分完），当一个人操作不了时输掉。先手一定赢输出 1，否则输出 0。

我们可以看一下公平组合游戏（Impartial Game）的定义。

1. 游戏有两个人参与，二者轮流做出决策，双方均知道游戏的完整信息。
2. 任意一个游戏者在某一确定状态可以作出的决策集合只与当前的状态有关，而与游戏者无关。
3. 游戏中的同一个状态不可能多次抵达，游戏以玩家无法行动为结束，且游戏一定会在有限步后以非平局结束。

题意所述的游戏确实为公平组合游戏。那这有什么用呢？

接下来介绍一下公平组合游戏的一些性质：

首先，由定义可知对于游戏中的各种状态只可能存在两种：以 该状态开始先手必胜 与 以该状态开始先手必败。为了方便，下面简称为 W 状态 和 L 状态。

其次，没有后继状态（从该状态开始进行一次操作后的状态）的状态一定是 L 状态，因为此时无法操作，该玩家也就输了。

然后，一个状态为 W 状态 当且仅当其至少有一个后继状态为 L 状态。显然，你有机会给对手留下 L 状态 就相当于你有方法获得了胜利。

最后，一个状态为 L 状态 需要它的所有后继状态都为 W 状态。这样，无论你怎么操作，都会给对手留下 W 状态，相当于你输了。

此外，若把 L 状态 与 W 状态 都看作节点，从一个状态到另一个状态的转移看作有向边，那么就能构成一张有向无环图，一般称之为博弈图。

以上这些性质应该还比较好理解吧。那这有什么用呢？

我们还需要三个定义：函数 \operatorname{mex}、SG 函数和SG 定理。

定义 \operatorname{mex} 函数的值为不属于集合 S 中的最小非负整数，即：

例如 \operatorname{mex}(\{1,3,4,7,8\}) = 0，\operatorname{mex}(\{0,1,3,4,7\}) = 2。

定义 SG 函数：对于状态 x 与其后继状态 y_1,y_2,y_3,\dots,y_n，有

而对于一个公平组合游戏，设其起点为 s，则 当 \operatorname{SG}(s) \not= 0 时，先手必胜。

若有多个起点 s_1,s_2,s_3,\dots,s_k 则当 \operatorname{SG}(s_1) \oplus \operatorname{SG}(s_2) \oplus \dots \oplus \operatorname{SG}(s_k) \not= 0 时，先手必胜。同时，该组合游戏的 \operatorname{SG} 值也为 \operatorname{SG}(s_1) \oplus \operatorname{SG}(s_2) \oplus \dots \oplus \operatorname{SG}(s_k)。

为什么呢？可以用数学归纳法证明，如此定义的 \operatorname {SG} 函数在等于 0 时等价于 L 状态，反之为 W 状态。这个定理便是 并非 大名鼎鼎的 SG 定理。

接下来的内容引用自 oi-wiki 中对于 SG 定理的证明。不想看严谨证明的可以跳过。

我们假设对于游戏状态 x'，其当前节点 s_1', s_2', \ldots, s_n'（对于任意 i 有

$s_1', s_2', \ldots, s_n'$ 符合 SG 定理，SG 定理便成立。 事实上这一个状态可以看作一个 Nim 游戏，对于某个节点 $s_i$，它可以移动到任意一个 $\operatorname{SG}$ 值比它小或比它大的节点。在有向图游戏中，当一方将某一节点 $s_i$ 移动到 $\operatorname{SG}$ 值比它大的节点时，另一方可以移动回和 $\operatorname{SG}$ 值和 $\operatorname{SG}(s_i)$ 一样的节点，所以向 SG 值较大节点移动是无效操作。 当移动到 SG 值较小的节点时，情况则会和 Nim 游戏一样，能够到达任何一个游戏状态 $x'$ 使得 $\operatorname{SG}(x')= \operatorname{SG}(s_1') \oplus \operatorname{SG}(s_2') \oplus \ldots \oplus \operatorname{SG}(s_n') < \operatorname{SG}(X)$（注意到前文已经假设 $x'$ 满足 SG 定理），但到达不了 SG 值为 $\operatorname{SG}(s_1) \oplus \operatorname{SG}(s_2) \oplus \ldots \oplus \operatorname{SG}(s_n)$ 的节点。 所以状态 $x$ 符合 SG 定理。

你可能会奇怪，为什么一个状态的 \operatorname{SG} 值也为 \operatorname{SG}(s_1) \oplus \operatorname{SG}(s_2) \oplus \dots \oplus \operatorname{SG}(s_k)？或者说为什么异或值会和状态的胜负有关？

为了方便理解，以一个有 5 堆石头的 Nim 游戏为例，假设这 5 堆石头的石头数分别为 1,9,4,6,5。根据 Nim 游戏的性质，有 \operatorname{SG}(x) = x。所以

最终输的状态显然为

那么我们就可以给为什么 \operatorname{SG}(x) = 0 时必输一个解释。

而当 \operatorname{SG}(x) \not= 0 时，先手可以取出一个 x = 当前 SG 值，就可以看作后手变为先手面对 \operatorname{SG}(x) = 0 的局面。

那么总可以找到这样一个 x 吗？从样例来说，取不出一个 15 啊。

假设 x 的二进制最高位 1 为 d，即 2^d \le x < 2^{d + 1}。根据异或定义，一定有奇数个 a_i 的二进制第 d 位为 1。满足这个条件的 a_i 一定也满足 a_i > a_i \oplus x，因而这也是个合法的取值。就样例而言，从第二堆取出一个 3 即可。

学完了就开始做题吧。

这道题中，对于一个有 i 个石子的堆，将它拆成 M 堆石子相当于将该游戏转化为 M 个石子数量为 \lfloor \dfrac{i}{M} \rfloor 或 \lfloor \dfrac{i}{M} \rfloor + 1 的子游戏，SG 值为这些子游戏的 SG 值的异或和。

然后枚举合法的 M，取这些 SG 值的 \operatorname{mex} 值，作为有 i 个石子的堆的 SG 值。因为石子数小于 F 的堆不能拆，SG 值便为 0，以此为边界条件从小到大求解 SG 值。

预处理完后，对于单次输入的每堆石子数量，将它们对应的 SG 值异或起来，cout << (res != 0) << ' '; 即可。

做完了？并非如此，这太暴力了，时间复杂度是 O(n^2) 的，过不了一点，考虑优化。

对于一个有 i 个石子的堆，将它拆成 M 堆石子相当于将该游戏转化为 i \% M 个石子数量为 \lfloor \dfrac{i}{M} \rfloor 的子游戏和 M - i \% M 个石子数量为 \lfloor \dfrac{i}{M} \rfloor + 1 的子游戏。

根据异或的性质，我们考虑 i \% M 与 M - i \% M 的奇偶性，只有奇数个的子游戏才能做出贡献。

诶，同时我们看到形似 \lfloor\dfrac iM\rfloor （上面相当于 n，下面相当于 i）是不是能想到整除分块？将 \lfloor\dfrac iM\rfloor 相同的数打包同时计算能大大降低时间复杂度。

同时，我们还能注意到 \lfloor\dfrac iM\rfloor 一定时，对应的 i \% M 与 M - i \% M 的奇偶性不变！证明可以参考 这篇题解：

当 \lfloor\dfrac iM\rfloor 为奇数时， \begin{aligned}M -i\%M = M - (i- M\times\lfloor \frac{i}{M}\rfloor)=M \times (1+\lfloor \frac{i}{M}\rfloor)-i\end{aligned} ，对于 \lfloor\dfrac iM\rfloor 为偶数， M + 1 后，奇偶性不变。

当 \lfloor\dfrac iM\rfloor 为偶数时， \begin{aligned}i\%M = i- M\times\lfloor \frac{i}{M}\rfloor\end{aligned} ， M + 1 后，奇偶性不变。

所以我们就能写出一篇时间复杂度为 O(n^{\frac{3}{2}}) 的代码了。

#include <bits/stdc++.h>
using namespace std;
#define f(n,m,i) for (int i(n);i <= m;++ i)
#define nf(n,m,i) for (int i(n);i >= m;-- i)
#define dbug(x) cerr << (#x) << ':' << x << ' ';
#define ent cerr << '\n';
#define max(a,b) (((a) > (b)) ? (a) : (b))
#define min(a,b) (((a) < (b)) ? (a) : (b))
#define ll long long
#define gc getchar_unlocked
#define pc putchar_unlocked
int ip(){//input，输入
    int num(0),fu(1);char c(gc());
    while (c > '9' || c < '0'){
        if (c == '-')   fu = -fu;
        c = gc();}
    while (c <= '9' && c >= '0')
        num = num * 10 + (c ^ 48),c = gc();
    return num * fu;
}
void op(int x){//output，输出
    if (x < 0)  x = -x,pc('-');
    if (x > 9)  op(x / 10);
    pc((x % 10) ^ 48);
}
int sg[100005],T,F,x,l;
bool vis[105];
int main(){
    T = ip(),F = ip();
    f(F,100000,n){//求解SG(n)
        memset(vis,0,sizeof vis),l = 2;//l相当于m，即分成的堆数
        while (l <= n){//整除分块
            int nl(n / l),r(n / nl);
            f((l == r),1,cnt){//当块长为1时只算一次，否则两次
                int ans(0),res(n % l);
                if (res & 1)        ans ^= sg[nl + 1];
                if ((l - res) & 1)  ans ^= sg[nl];
                //考虑 i % m 与 m - i % m 的奇偶性
                ++ l,vis[ans] = true;//标记相应的SG值
            }
            l = r + 1;
        }
        while (vis[sg[n]])    ++ sg[n];//算mex
    }
    while (T --){
        int n(ip()),res(0);
        f(1,n,i)
            x = ip(),res ^= sg[x];
        op((res != 0)),pc(' ');//算SG的异或和输出
    }//dbug(clock() / 1000000.0)本地跑样例1s+，洛谷神机tql！
    return pc('\n'),0;
}
/*
g++ p3235.cpp -o code
./code

4 3
1 1
1 2
1 3
1 5

*/