sg 函数 & P3179 [HAOI2015] 数组游戏题解

· · 题解

博弈论公平组合游戏从入门到这道入土题。

sbno333 手把手教你 sg 函数。

前言

2025.8.2 更新：删除一些问题，添加复杂度证明，添加笔者最新理解。

发现其它题解写的并不清晰，缺少一些证明，导致在看题界的时候遇到了极大的困难，同时为了纪念首 A 黑题，所以有了这篇题解。

首先，不是所有游戏都要用到博弈论知识，很多游戏递推解决即可，但有些游戏需要用到，具体按情况而论，一般的，看着像 Nim 游戏的都是递推（诈骗）或者贪心之类的东西，看着和 Nim 半毛钱没有的是博弈论。

前置知识

动态规划思想，异或，整数分块，\text{mex}，可以上 OI 维基自主学习。

游戏

我们考虑有两个人（Alice 和 Bob）玩游戏，只有输和赢，并且不没有同输同赢的情况，游戏保证无论二人如何操作，都不会一直无法停止。现在，二人绝对聪明，谁赢？

事实上，除去 最长待机 这种难评的游戏，都在最开始确定了胜负。

我们可以把每种游戏可能形成的局面设成一个状态。

每个状态都向一步之后能到的状态连一条有向边，由于保证能不会无法停止，所以没有环，此时游戏形成了一个 dag。

我们可以设 dp_S 表示 S 状态下，Alice 是否必胜，必胜是 1，否则是 0。

对于走投无路的节点，我们判定其 dp_S 的值，然后向前递推。

具体的，我们状态中记录此时谁先手，然后根据谁先手，在所有状态中到达的状态中，取最大或最小值即可。

然而游戏一般状态很多，公平组合游戏具有一定优秀的性质，能够帮我们大幅降低复杂度。

一般公平组合游戏

两个人轮流操作，没有平局，每个人每次能进行的操作与人无关，并且能结束。比如国际象棋就不是这类游戏，因为它有平局，而且你只能动自己的棋子，不能动对方的，无法操作的一方输。

sg 函数

在这之前，我们应当学习 Nim 游戏，这个游戏在博弈论学习中起到极其重要的地位。

Nim 游戏

如题，有 n 堆石子，每堆石子有若干个石子，不能不取，每次可以选取一堆石子，取走若干石头。

下文中用 \oplus 代替按位异或。

这道题有一个必胜策略就是当石子堆石子数量异或和为 0 时，先手必败，否则必胜。

具体的，当异或和为 0 时，显然我们操作后肯定改变了某个石堆，设其它石堆异或和为 x，这个石堆原本也一定为 x，改变后为 y<x，对于两个不同的数，其异或和一定不为 0，因此取完后为异或和不为 0。

对于不为 0，设这个值为 x，其最高位为 1，显然存在一个石堆，其和异或和的最高位对应也是 1，设其有 y 个石子，此时其他石子堆异或和为 x\oplus y，由于 x,y 在 x 最高位都是 1，因此 x\oplus y 那一位为 0。

我们此时只需要将 y 变得使 x=0，即 x\oplus y=y，显然 x\oplus y 不会随操作 y 而改变（操作当前不会改变其他石子），可以这么操作当且仅当原来的 y 比 x\oplus y 大，这样才能将 y 取到 x\oplus y。

问题变成了 y 异或上一个没有 y 位数多，且那个数最高位 y 对应位也是 1 的数（上述提到的 x 具有的性质）与其异或后能否比 y 小。

对于比 x 最高位高的位，显然异或后不改变，不考虑。

对于 x 最高位，异或后 y 对应位减少（从 1 到 0)，其他位怎么增加也比不上，所以正确，即可以将异或和从 \not=0 变为 0。

一个人输的时候显然石子堆异或和为 0，所以 \not=0 时不为输的状态。

所以如果先手时异或和 \not=0，总是可以给到对方 =0，而对方又只能返回 \not=0，这样下先手必胜。

如果先手为 0，则只能把 \not=0 给到对方，对方再采用上述策略，先手必败。

所以结论就是判断异或和是否为 0。

从 Nim 升级开始代入 sg 定理

我们不妨升级 Nim 游戏，每次不但可以取走，还可以放入，但不能不操作，为了游戏的有限，每次放入后如果满足某个条件，之后双方将无法放入，而且每次放入对放入的数量有限制。

对于异或和 \not=0，显然可以看作只能减少，然后显然可以把异或和变为 0。

对于 =0，显然还是要改变，因此还是会重新变为 \not=0 给对方。

因此这个游戏与上述普通 Nim 游戏必胜策略一致，与放入的条件之类无关，但当减少有限制时，游戏结果或受到影响。

sg 函数及定理

对于公平组合游戏，我们设置的状态可以是 dp_S 表示局面初始为 S 时，先手是否必胜。因为公平组合游戏我们并不关心当前到底是该谁操作。此时我们转移就只有简单的寻找能到达的状态中是否有 0，若有，则 dp_S=1，否则 dp_S=0。当然，此时还是复杂度很高。我们可以模拟 Nim 游戏进行考虑，这样我们或许能借用异或的性质来增速。设 sg(S) 表示状态 S 等价于 Nim 游戏中一个有 sg(S) 个石子的石堆。如果 S 状态指向 P 集合中每一个状态，我们有 sg(s)=\text{mex}_{T\in P} sg(T)。由上面的升级 NIM 容易得出。如果不借助性质，此时 sg(S)\not=0 对应原来的 dp_S=1，sg(S)=0 对应原来的 dp_S=0。容易看出确实等价。不过 sg(S) 有一个很大的性质，可以让我们优化转移。那就是如果当前状态 S 可以分成若干互不影响的子游戏，每次选取一个子游戏进行操作，比如 Nim 取石子可以分成 n 个子游戏，每个子游戏都是一堆石子，显然取走这堆石子不会影响其他石子堆。我们设这些子游戏组成集合 G。我们有 sg(S)=\oplus_{T\in G}sg(T)。

证明的话就是数学归纳法。对状态 S 操作一次到的状态相当于对于 T\in G，对恰好一个 T 进行一次操作。

根据上文，一个状态 A 操作之后成为状态 B，只有 sg(B)<sg(A) 才有意义，所以我们只保留这一种。

如果对 S 操作一次之后，这个性质成立，根据数学归纳法，最终无法操作状态显然也只能分成若干无法操作的子游戏，便可以得证。

于是我们要证明的东西等价于如下问题：

一个序列 a 的异或和为 x，请问对于任意 0\le y<x，是否存在 t,p，使得 p<a_t，并且将 a_t 修改为 p 之后序列异或和为 y。

我们分析一下，相当于 x\oplus a_t\oplus p=y。

推导可得 (x\oplus y)\oplus a_t=p。

因为 y<x。

因此存在某一位二进制，使得更高位二者相等，x 这一位是 1，y 是 0，异或和后就是这一位最高，因为原序列的异或和 x 这一位是 1，因此必然能找到一个这一位是 1 的数 a_t，异或和之后得到的 p 这一位必定是 0，更高位和 a_t 相等，因此 p<a_t，因此得证！

我们练习一下，尝试给出 Nim 游戏 sg 函数。

每堆石子都是一个子游戏，0 个石子 sg 值为 0，i 个石子可以转移为 0\sim i-1 任意数量石子，数学归纳可以得出 sg 值为 i。具体的如果，0\sim i-1 成立， sg(i)=\text{mex}_{j=0}^{i-1} j=i。

最后大游戏的 sg 就是每个子游戏 sg 的异或和，即石子数量的异或和。此时如果不是 0 先手赢，否则后手赢。

我们梳理一下，一个游戏可以分成若干子游戏，每个子游戏为一个有向无环图，终点 sg 值为 0，每个节点为其后继的 \text{mex}，游戏的 sg 值为子游戏 sg 值的异或和，如果游戏的 sg 值为 0，先手必败，否则必胜。

这里给出一个性质：有 mex 得出某个状态的 sg 值一定在 O(\sqrt m) 以内，其中 m 为状态所在子游戏构成的图的边数。

这道题的正式题解

翻格子游戏的性质

我们设每次选择一个白色的格子 i，选择一个满足条件的 k，翻转 S_{i,k} 集合内的格子，保证当前格子一定被翻转，且游戏能结束。

我们可以将游戏转化为每个格子有一个数，原游戏中白色初始是 1，黑色初始为 0。

每次可以选择一个非 0 的数进行操作，当前数的值减一 ，S_{i,k} 的其他数加一。

游戏中，显然白色对应奇数，黑格对应偶数，我们只需要证明这个游戏与原游戏等价（必胜判定相同）。

设原游戏先手为必胜方，显然可以按照原游戏策略进行，只翻转奇数，监督必败方是否也只反转奇数，如果翻转偶数，将其变为奇数，则先手再次对那个格子进行翻转，可以证明奇偶性可以与后手操作前一样，使得后手在奇偶性上操作无效，重新变回自己，而先手由于前提是必生，所以总有奇数可以翻，0 是偶数，于是可以证明新游戏也是必胜方。

如果原先后手必胜，仿照上述，易证。

所以等价。

结论就是可以分成 w 个子游戏，第 i 个子游戏只有第 i 原来的白格是 1 其他都是 0。

而我们每次都是在一个子游戏上进行的，你可以能认为这仍然会互相影响，但其实不是，这个序列在现实中表现为每个子问题的序列对应位置的和，如果这个位置是 0，则子游戏都为 0，不能操作。否则一定能看作一个子游戏进行的一次操作，因此可以分解。

这道题目求 sg 的具体方法

于是这样我们就将其分解成了若干子游戏，并且始终存在分解方案，这时候我们不妨设 sg(x) 表示只有 x 为白格，我们考虑列式子。

我们选择 k=1，此时得到游戏结束状态，sg 为 0。

选择 k=2，此时转化为只有 2x 为白色，为 sg(2x)。

选择 k=3，此时转化为 2x,3x 为白色，不妨再次按照刚刚的结论分解，分解为只有 2x 和只有 3x 为白色两个子游戏，按照 sg 定理，答案为起点 sg 的异或和，所以此时为 sg(2x)\oplus sg(3x)。

以此类推。

于是我们得到了 sg(x)=\text{mex}(0,\text{mex}_{i=2}^{\frac n x}\oplus_{j=2}^i sg(j))，即 sg(x)=\text{mex}(0,sg(2x),sg(2x)\oplus sg(3x),sg(2x)\oplus sg(3x)\oplus sg(4x)\dots)。

我们可以从 n 枚举到 1，暴力求出 sg(i)，可以做到 O(w) 处理询问，但预处理时间复杂度高达 O(n^2)，不能接受。

于是考虑优化。

有一些 sg(i) 可能是相同的，我们考虑这段优化。

整数分块引入

可以发现，对于 \lfloor\frac n x\rfloor=\lfloor\frac n y\rfloor，有 sg(x)=sg(y)。

显然，它们 \text{mex} 内部项数相同，对于每一项，我们发现如果 sg(2x)=sg(2y),sg(3x)=sg(3y)\dots，则猜想成立。

当 x,y>\frac n 2 时，显然 sg(x)=sg(y)=0，且 \lfloor\frac n x\rfloor=\lfloor\frac n y\rfloor 成立。

对于 tx,ty，如果 \lfloor\frac n x\rfloor=\lfloor\frac n y\rfloor 成立，则 \lfloor\frac n {tx}\rfloor=\lfloor\frac {\lfloor\frac{n}{x}\rfloor} {t}\rfloor=\lfloor\frac {\lfloor\frac{n}{y}\rfloor} {t}\rfloor=\lfloor\frac n {ty}\rfloor，由于前者已经在题设中成立，因此结论成立，因此当 tx>x,\lfloor\frac n {tx}\rfloor=\lfloor\frac n {ty}\rfloor 时，sg(tx)=sg(ty) 成立，sg(x)=sg(y) 可以推导成前式题设，对于 t>1 都成立，x 成立，由于当 tx>\frac{n}{2} 时成立，因此对于 x 成立。使用的嗜血数学归纳法，没看懂可以自行推导。

因此可以整数分块处理每一种 \frac{n}{x}，处理每一个也可以整数分块，对于 \frac{n}{tx}=\frac{n}{px}，显然 sg(tx)=sg(px)，因此内部也是根号，但由于外部循环枚举的不同，内部根号也不同，最后得 O(n^\frac{3}{4}) 时间复杂度。

证明：

看之前可以先移步整数分块复杂度证明。

对于每个 x，我们相当于要枚举 k 等于 2,3,4 一直到 \lfloor\frac{n}{x}\rfloor。

由于 sg(x) 只取决于 \lfloor\frac{n}{x}\rfloor。

我们处理 x 的复杂度相当于 \lfloor\frac{n}{kx}\rfloor 有几种不同的值。

进一步的，\lfloor\frac{\lfloor\frac{n}{x}\rfloor}{k}\rfloor，根据整数分块，答案为 O(\sqrt \frac{n}{x}) 级别的。

当 x 大于 \sqrt n 时，只有 \sqrt n 种 sg 可能不同的取值，\sqrt \frac{n}{x} 最大取到 O(n^{\frac{1}{4}})，得到 O(n^\frac{3}{4})。

当 x 小于等于 \sqrt n 时，每个 x 我们都觉得它能取到，那就是 \sum_{x=1}^{\sqrt n}\sqrt \frac{n}{x}<\sum_{c=0}^{\log_2(\sqrt n)}2^c\sqrt \frac{n}{2^c}=\sqrt n \sum_{c=0}^{\log_2(\sqrt n)}\sqrt{2}^c=\sqrt n\frac{(\sqrt 2)^{\log_2 \sqrt n+1}-1}{\sqrt 2-1}=\sqrt n\frac{(2\sqrt {n})^{0.5}-1}{\sqrt 2-1}。

得到 O(\sqrt n\times n^{\frac{1}{4}}) 得到 O(n^\frac{3}{4})。

代码

#include<bits/stdc++.h>//可以自行阅读理解
using namespace std;
int s[100009][2];
int n;
int sg(int x){
    if(x>sqrt(n))return s[n/x][0];return s[x][1];
}
int z[100009];
int inn;
int mex[2400009];
void inite(){
    for(int i=1,j=0;i<=n;i=j+1){
    j=n/(n/i);
        z[++inn]=j;
    }
    for(int t=inn;t>=1;t--){
        int yh;
        yh=0;
        mex[yh]=t;
        for(int i=z[t]*2,j;i<=n;i=j+z[t]){j=n/(n/i)/z[t]*z[t];
            mex[yh^sg(i)]=t;
            if(((j-i)/z[t]+1)&1){
                yh^=sg(i);
            }
        }
        int ans;
        ans=0;
        while(mex[ans]==t){
            ans++;
        }
        if(z[t]>sqrt(n))s[n/z[t]][0]=ans;
        else s[z[t]][1]=ans;

    }
}
signed main(){
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    inite();
    int q;
    cin>>q;
    for(int i=1;i<=q;i++){
        int m;
        cin>>m;
        int yh;
        yh=0;
        for(int i=1;i<=m;i++){
            int x;
            cin>>x;
            yh^=sg(x);
        }
        cout<<(yh==0?"No":"Yes")<<endl;
    }
    return 0;
}

拓展