SG函数_杂项

SG 函数

属于博弈论的一种构造吧。

就有些东西你第一次接触就会感觉很莫名其妙，看了证明后觉得是不是还存在第二种解，直到对它的理解逐渐深入。

P2197 【模板】Nim 游戏

$n$ 堆石子，第 $i$ 堆有 $a_i$ 个，每个人每次可以选一堆拿取 $[1,a_i]$ 个石子，不能操作的玩家输。

问双方采取最优策略下先手还是后手赢。

首先你考虑只有一堆石子是什么情况。

你发现这可以连成一个有向图，数量为 $i$ 的状态连向数量为 $j<i$ 的状态，其中 $0$ 没有出度为必败态，其他点是必胜态。

但如果我现在有两堆石子怎么办？

你发现你每次可以移动一堆石子，我们可以设一个二元状态 $(x,y)$，其中 $(0,0)$ 为必败态，$(x>0,0)$ 和 $(0,x>0)$ 是必胜态，那剩余的状态呢？

对于这种把多个互不相同的游戏组合到一起，每个玩家每次可以在一个游戏中走任意一步，不能走的玩家输，我们称这种游戏为公平组合游戏。

公平组合游戏的策略并不局限于单个游戏的必胜或必败态，我们需要引入更复杂的量来把这类游戏和它的每个部分联系在一起。

SG 函数

首先我们需要有向图博弈的概念，有一个棋子在一个有向图上，每个点代表游戏的一个状态，每次玩家可以沿有向边将棋子移动一步，不能移动的玩家输。

这是我们所熟知的博弈理论，我们都学会了判正负平，以及最小步数最大步数。

公平组合游戏体现在这里就是有多个棋子，若多个游戏是同一结构那就在同一张图上，否则在不同的图上（可以看作不连通，反正是有向图）。

一个节点的 SG 函数 定义为其出点的 $s_x=\text{mex}_{x\to v}\{s_v\}$，其中 $\text{mex}\ S$ 定义为 $\min_{i\ge 0}\{i|i\notin S\}$。

从这里我们可以看出只有单个棋子时 $s_x>0$ 即是必胜态，因为它一定可以走到一个 $s_x=0$ 的状态，而必败态 $s_x=0$。

接下来是有意思的部分，对于一个初始状态为 $a_1,a_2,a_3,\cdots,a_n$ 的组合博弈，游戏是必败态当且仅当 $\bigoplus_{i=1}^ns_{a_i}=0$。

这是一个非常有意思的构造，这个结论告诉我们两件事：

• 对于任意一个 $\bigoplus_{i=1}^ns_{a_i}=0$ 的局面，我们不可能移动一步使得其仍为 $\bigoplus_{i=1}^ns_{a_i}=0$。
• 对于任意一个 $\bigoplus_{i=1}^ns_{a_i}\ne0$ 的局面，我们总能移动一步使得其变为 $\bigoplus_{i=1}^ns_{a_i}=0$。

我们挨个论证。

首先第一个很简单，$s_x=i$ 的后继节点 $v$ 必然满足 $s_v\ne i$，否则 $s_x>i$，假设不成立。

第二个也很好论证，它相当于告诉我们有一个序列 $a$，满足 $\bigoplus_ia_i\ne 0$，你可以把任意一个 $a_i$ 变为 $[0,a_i-1]$ 中的整数，让你构造一个方案使得变化后 $\bigoplus_ia_i= 0$。

我们直接取出任意一个二进制最高位与 $\bigoplus_ia_i$ 相同的 $x$，则 $x\oplus(\bigoplus_ia_i)<x$，也就是说我们把 $x$ 换成 $x\oplus(\bigoplus_ia_i)$ 即可完成任务。

对于 nim 游戏，你可以得出大小为 $i$ 的石子堆状态 $s_i=i$，所以它的解法就是判断异或和是否为 $0$。

P4301 [CQOI2013] 新Nim游戏

第一个回合双方可以抱走 $\ge 0$ 堆整堆的石子，但不能抱空，第二个回合开始玩 nim 游戏，问能否获胜，如果能获胜，求第一回合最少拿多少。

考察重点并不是博弈，就有点无聊。

你发现先手可以决定游戏初始不能有哪些，后手可以决定游戏初始最终留哪些。

然后你发现先手不可能输，只需要剩一堆即可。

若先手留给后手一个能凑出异或和为 $0$ 的集合，则先手必输，所以先手的策略是留下一个无论如何删剩下的集合异或和也凑不出 $0$。

也就是不存在一个非空子集异或和为 $0$，越听越像线性基。

于是你只需要贪心线性基， 从大到小插，插不进去就取走。

CF850C Arpa and a game with Mojtaba

一些数字，你每次可以提出一个至少被其中一个数整除的 $p^k(p\in\mathbb P,k>0)$，然后把所有 $p^k$ 整除的数都除以 $p^k$，不能操作的玩家输。

$n\le 100,a_i\le10^9$。

你发现这个题跟序列没什么关系，你把数去重了还是等价的。

于是考虑每个质数是独立的，拆成若干个独立的博弈，每个质数只关心它的每个幂次是否出现过，可以状压，记忆化搜索即可。

CF1823E Removing Graph

给定一个置换（由若干环组成的无向图），每次可以选一个大小为 $[l,r]$ 的连通块并将其删掉，不能操作的玩家输。

$n\le2\times 10^5$。

首先肯定把每个环拆开，然后我们发现删一个环有可能删空，也有可能删成一条链，删一条链有可能删空，删成一条链，删成两条链（这两条链就变成了独立的部分，使用异或合并）。

设 $f_i$ 为大小为 $i$ 的环的 SG 值，$g_i$ 为长为 $i$ 的链的 SG 值，则：

$$f_0=0,g_0=0\\f_i=\mathop{\text{mex}}\limits_{j=\max(0,i-r)}^{i-l}g_j,g_i=\mathop{\text{mex}}\limits_{j=\max(0,i-r)}^{i-l}\mathop\text{mex}\limits_{k=0}^jg_k\oplus g_{j-k}$$

你考虑设一个 $h_j=\mathop\text{mex}\limits_{k=0}^jg_k\oplus g_{j-k}$ 就能记忆化转移了，但这是 $\Theta(n^2)$ 的。

冥思苦想，完全没思路，打表启动！

许多 SG 函数题都是打表解决的，考场上要及时意识到这一点。

PathGame

给定一个 $2\times n$ 的黑白网格，保证初始合法，双方需要时刻保证网格的第 $0$ 列与第 $n+1$ 列通过白色方格四联通，每人每次选一个白点染黑，无法操作输，问先手是否有必胜策略。

$n\le 1000$。

$\rm SG$ 函数。

还是太生疏导致的，$\rm SG$ 函数需要你用尽可能简洁的问题组合出原问题，而不是在原问题上瞎乱做。

我们发现一大段白很简洁，且互不干扰，于是我们每两个黑列中间的部分截出来作为一个游戏。

状态有长度和 $\rm type$，后者包括左右限制相同，左右限制不同，左右只有一边有限制，左右都无限制。

阶梯 Nim

Nim 游戏，但拿掉第 $i$ 堆上的石子会扔到 $i-1$ 堆上，拿掉 $1$ 上的石子相当于直接拿掉。

只需要对奇数堆做 Nim 即可，若后手操作奇数堆那么相当于做 Nim 游戏，若后手操作偶数堆那我们可以跟一手，把刚刚的石子再扔到下一个偶数堆上。

如果奇数堆玩 Nim 先手必胜那么先手使用上面的策略可以达到必胜，否则后手使用上面的策略可以达到必胜。

P5363 [SDOI2019] 移动金币

一个长为 $n$ 的 $01$ 序列，有 $m$ 个 $1$，每次可以选一个 $1$ 左移任意正数步，不能跨过其他的 $1$，不能操作的人输（此时 $m$ 个 $1$ 堆在最左边）。

问有多少种初始序列满足先手必胜。

$n\le 10^5,m\le 50$。

把金币的移动看作空位的移动，你发现空位就是石子，每次把空位扔给右边的一堆，这就是一个左右互换的阶梯 Nim。

运用刚刚的知识，我们很快有了一个 $n^2m$ 的做法：$f_{i,j,0/1}$ 表示从右往左填了 $i$ 个格，奇数位置上的 $\oplus=j$，最后填的是奇数段/偶数段，转移枚举下一段填多长。

仔细思考发现，你其实并不在乎序列的结构，你所做的其实只是把 $n-m$ 个空位分配给 $m$ 个数，使得奇数段长异或起来不为 $0$。

不妨用 $\binom n m$ 减去异或起来 $=0$ 的方案，这么做显然更友好。

然后你发现可以按位算了，每位出现偶数次，还要保证加起来 $\le n'=n-m$，假设奇数段有 $p=\lceil m/2\rceil$ 个。

我们设 $f_{i,j}$ 表示填了前 $i$ 位，加起来是 $j$，转移式是 $f_{i,j}\gets \binom{p}{2k}f_{i-1,j-2k2^{i}}$。

然后你发现状态数是 $n\log n$ 的，转移的 $k$ 是 $O(m)$ 的，所以是 $O(nm\log n)$ 的。