自动搬运

查看原文

来自洛谷，原作者为

	sbno333 不进北省不改签！！！

搬运于2025-08-24 21:46:10，当前版本为作者最后更新于2024-05-09 11:47:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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

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;
} 

拓展

• 反常游戏，无法操作的一方获胜，具体可以参考 OI 维基举得 Nim 游戏在反常下的值，对应 sg 函数合并求结果时按照反常 Nim 进行判断即可。