博弈论小记

# 博弈论基本框架 - **公平组合游戏** 有一个游戏状态 $G$ ，某些状态定义为终止态，得到终止态者为负。 玩家的操作可以使得状态发生变化 : $G\rightarrow G'$。 且满足转化关系不存在环 (否则游戏可能一直进行下去)。 满足如下特征 : - 两个玩家面对同一个状态 $G$ ，其可能的目标状态集合是相同的。（决策公平） - 两个玩家都知道有关游戏的所有信息。（无隐藏信息） - 不包含随机成分。（无随机过程） - 只有赢或输，没有平局。（无平局） 一般而言，都约定 ： 两个(绝顶聪明的)玩家采取对自己最有利的决策，且轮流作出决策。 - **必胜态和必败态** 先手存在必胜策略的状态 $G$ ，称之为必胜态，又作 $\rm N$ 态。 反之称作必败态，又作 $\rm P$ 态。显然，所有的终止态都是必败态。 若某个态 $G$ 满足其转移中存在一个 $\rm P$ 态，则 $G$ 为 $\rm N$ 态，因为先手可以把必败态送给对面。 反之，则必然把 $\rm N$ 态送给对面，此时 $G$ 是 $\rm P$ 态。 利用这些基本知识已经可以做一些初等的博弈论题目。 - **「一堆石子」** **题意** : 有一堆 $n$ 个石子，对于每个 $k$ 给出集合 $S_k$ ，当还剩 $k$ 个石子时，拿去石子的个数 $c$ 必须 $\in S_k$。 无法操作的人输。问是否先手必胜。 记 $[k]$ 为一堆 $k$ 个石子的状态。$f[k]$ 表示 $[k]$ 是否为 $\rm N$ 态。 边界 : $f[0]=0$。 转移 : $f[k]=\neg\min\limits_{c\in S_k}f[k-c]$ 复杂度为 $O(\sum |S_k|)$ ，本质上是 $\rm DAG$ 上的 $\rm DP$。 - [HDU 2897邂逅明下](http://acm.hdu.edu.cn/showproblem.php?pid=2897) **题意** : 有一堆 $n$ 个石子，每次可以拿去 $p\sim q$ 个，无法操作的人输。问是否先手必胜。 这是第一题中 $S_k=[p,q]$ 的特殊情况。 对于 $[1]\sim [p-1]$ ，为 $\rm P$ 态。 对于接下来的 $[p]\sim [p+q-1]$ ，都可以一步到达 $\rm P$ 态，故为 $\rm N$ 态。 对于 $[p+q]\sim[p+q+p-1]$ ，能到达的范围在 $[p]\sim [p+q-1]$ 内，故为 $\rm P$ 态。 如此归纳，不难发现 : 若 $n\bmod (p+q)\in [1,p]$ 则先手必胜，反之必败。 当然，打表观察也是一个非常好的办法。 - **带权博弈** 游戏中的每种转移方式都有不同的权值，游戏的得分是每一步转移的权值之和。 在首要目标是获胜的前提下，还可能希望最大化/最小化得分。 显然，胜负博弈是带权博弈的子集。 - **「一堆石子」贰** **题意** : 有一堆 $n$ 个石子，对于每个 $k$ 给出二元组集合 $S_k$。 当还剩 $k$ 个石子时，拿去石子的个数 $c$ 必须满足 : 存在 $(a,b)\in S_k$ ，使得 $a=c$，且这一步会获得 $b$ 分。 在首要目标是获胜的前提下，先手 A 希望最小化得分，后手 B 希望最大化得分。问最终胜负以及得分。 记 $f[k]$ 表示 $[k]$ 是否为 $\rm N$ 态。$g[k][A/B]$ 为从 $[k]$ 开始 $A/B$ 先手的游戏的最终得分。 若 $f[k]=1$ 即先手必胜 ，则这一步会在所有后继状态 $[k']$ 中选择一个满足 $f[k']=0$ 且 $g[k']$ 最好的。 即 $\begin{cases}g[k][A]=\min\limits_{(a,b)\in S_k,f[k-a]=0}g[k-a][B]+b\\g[k][B]=\max\limits_{(a,b)\in S_k,f[k-a]=0}g[k-a][A]+b\end{cases}$ 若先手必败，则不设 $f[k']=0$ 的限制。 即 $\begin{cases}g[k][A]=\min\limits_{(a,b)\in S_k}g[k-a][B]+b\\g[k][B]=\max\limits_{(a,b)\in S_k}g[k-a][A]+b\end{cases}$ - [P1857 质数取石子](https://www.luogu.com.cn/problem/P1857) 这是上一题中 $S_k=\big\{\big({\rm Prime},1\big)\big\}$ 的特殊情况。 不同的是，游戏的胜负会影响决策 : 必胜者希望权值小，必败者希望权值大。这反倒统一了两个人的决策。 记 $f[k]$ 表示 $[k]$ 是否为 $\rm N$ 态。$g[k]$ 为从 $[k]$ 开始的游戏的最终权值。 若 $f[k]=1$ 即先手必胜 ，则这一步会在所有后继状态 $[k']$ 中选择一个满足 $f[k']=0$ 且 $g[k']$ 最小的。 否则在所有后继状态中取 $g[k']$ 最大的。 单次询问复杂度为 $O\big(\sum_{k=1}^n\pi(k)\big)=O(n^2/\log n)$。 - [P4363 [九省联考2018]一双木棋chess](https://www.luogu.com.cn/problem/P4363) 记落子状态为 $G$ ，先手方为 $T$ ，则 $(G,T)$ 为一组状态。 考虑如何简洁地表示一种落子状态，不难发现，有子和无子的界限是一条左下到右上的路径，且只能向上或向右。 用 $1$ 表示向上 $0$ 表示向右，则能用长为 $n+m$ 的 $01$ 序列来表示某个 $G$。 本质不同的局面个数为 $2\times \binom{n+m}{n}$ 约为 $3.7\times 10^5$ 级别。 每个局面的转移为 $O(n)$ 级别。 用 `unordered_map` 记录状态然后记忆化搜索，复杂度即为 $O\Big(\binom{n+m}{n}n\Big)$。 [评测记录](https://www.luogu.com.cn/record/47109330) # $\bf SG$ 函数与 $\bf SG$ 和 - **定义**: 约定终止态的 $SG$ 函数值为 $0$。 定义 ${\rm mex}(S)$ 为集合 $S$ 中最小的未出现的自然数。 (要求 $S\subseteq N$) 设 $G$ 能转移到状态集合 $T_G$ (转移关系可以看成`DAG`)，那么定义 $$SG(G)={\rm mex}\big\{SG(V):V\in T_G\big\}$$ 人话就是 : 能转移到的状态集合的 $SG$ 函数值的 $\rm mex$。 - **性质** : $SG(G)=0$ 的 $G$ 是必败态，反之是必胜态。 若 $SG(G)=0$ ，则代表后继的 $SG$ 没有 $0$ ，反之则代表有 $0$。 从终止态出发归纳即可证 $SG=0\Leftrightarrow$ 必败态。 对于单个游戏，$SG$ 函数并未给我们带来任何便利。（似乎不能比记录 $\rm N/P$ 态做得更多） 下面我们将看到， $SG$ 函数是如何将多个独立的游戏组合到一起的。 - $\bf SG$ **和** 考虑两个人同时面对多个游戏，但每次只能操作其中一个。 把游戏间的并列关系定义为 $+$。如 $A+B$ 产生游戏二元组 $(A,B)$ ，在一次操作后可能变为 $(A',B)$ 或者 $(A,B')$ ，类似地可以定义游戏多元组的 $SG$ 函数。 (若暂时无法理解并列关系和互相独立的准确意义，可以先看下方“Nim”问题) **定理** : $SG(A+B)=SG(A){\ \rm xor}\ SG(B)$。 这给出了游戏合并后的 $SG$ 函数与原 $SG$ 函数的简洁关系。 **证明** : 记 $y=SG(A){\ \rm xor}\ SG(B),\ G=(A,B)$。 等价于证明 $\begin{cases}\forall_{x<y},?_{G\rightarrow G'}SG(G')=x\\\forall_{G\rightarrow G'}SG(G')≠y\end{cases}$ (其实就是把 $\rm mex$ 用逻辑语言写出) 由于我们在 $DAG$ 上归纳(边界为终止态)，可以认为对于所有的后继状态 $G'$ ，结论已成立。 - $\forall_{x<y},?_{G\rightarrow G'}SG(G')=x$ 记 $d=x{\ \rm xor\ }y$ ，其**最高位**为 $k$ 。设 $A'$ 为 $A$ 能转移到的某个状态， 同理有 $B'$。 显然 $x,y$ 中必有一个第 $k$ 位为 $1$。 若 $x$ 的第 $k$ 位为 $1$ ，又由于 $k$ 是最高位， $x$ 需要把 $y$ 前面的东西都抵消掉。这样， $x$ 比 $k$ 高的部分和 $y$ 相同，而第 $k$ 位比 $y$ 大，与 $x<y$ 矛盾。 因此，$y$ 的第 $k$ 位为 $1$，故 $SG(A),SG(B)$ 中必有一个第 $k$ 位为 $1$。 不妨设 $SG(A)$ 的第 $k$ 位为 $1$ ，这样 $SG(A){\ \rm xor\ }d$ 会消去第 $k$ 位，且更高位不变，结果一定会变小。 即 $SG(A){\ \rm xor\ }d<SG(A)$。 这样，由 $SG$ 函数的定义，必然存在一个 $SG(A')=SG(A){\ \rm xor\ }d=x{\ \rm xor\ }SG(B)$ ( 代入 $d$ )。 即存在 $SG(A'+B)=SG(A'){\ \rm xor\ }SG(B)=x$。 - $\forall_{G\rightarrow G'}SG(G')≠y$ 若存在 $SG(A'+B)=SG(A'){\ \rm xor\ }SG(B)=SG(A){\ \rm xor\ }SG(B)$ ，则有 $SG(A)=SG(A')$ ，矛盾。 不同种类的游戏在求出 $SG$ 函数后都能用 $SG$ 和来合并。且两个 $SG$ 函数相同的游戏在合并时是等价的。 - **$\bf Nim$** [P2197 【模板】nim游戏](https://www.luogu.com.cn/problem/P2197) 有 $N$ 堆石子，两个人轮流操作，每次可以把某一堆石子拿去若干。没有石子定义为终止态。 求 $N/P$ 态的判定方法。 我们先来观察**单个堆**的 $SG$ 函数。记 $[k]$ 为一堆 $k$ 个石子的状态。 首先，若该堆为空，则为终止态， $SG([0])=0$。 接下来， $[k]$ 可以转移到 $[0]...[k-1]$ 的任意一个，归纳可证 $SG([k])=k$。 现在来考虑多堆石子的情况，使用 $SG$ 和，异或起来即可判定是否必胜。 至于必胜策略，每次需要将异或和变为 $0$ 给对方。 查看异或和的最高位，选出一个包含该位的数，将这一位置为 $0$。 后面的位无论怎样变化，都会比原来的值小，那么随意安排，把其余非 $0$ 位恰好抵消即可。 > 例 : 有 $\begin{cases}1010000\\ 0001000\\ 1000010\end{cases}$ , 那么异或和为 $0011010$。 > 所以,选择 $1010000$ 来操作,将其变为 $1001010$ 异或和就变为 $0$ 了。 - $\bf Take\ Away$ 有 $m$ 个石堆,包含 $n$ 个石子，每一轮可以取走 $1...k$ 个棋子，不能操作者负。 先来考虑单堆。 当 $n\leq k$ 时，总能任意拿,则有 $SG(n)=n$。 当 $n=k+1$ 时，最近的 $0$ 距离是 $k+1$ ，无法达到，所以 $SG(k+1)=0$。 然后对于 $n=k+1$ 也同样拿不到上一个 $1$ ，则 $SG(k+2)=1$。 如此可得 $SG(n)=n\bmod (k+1)$。 多堆只需求 $SG$ 和即可。 - $\bf Hungergame$ 有 $m$ 个箱子，每个箱子中都有若干石子，双人博弈，每一轮可以采取下列操作之一: - 打开**若干个**箱子 - 将某个箱子中的石子取出若干。 由于可以一次打开多个箱子,这些游戏是不独立的，不能直接套用 $SG$ 和。 当所有的箱子都打开的时候，就是经典的 $\rm Nim$ 游戏了。 考虑先手打开什么，若开了异或和不为 $0$ 的箱子集合，相当于送给对面一个 $N$ 态的 $\rm Nim$。 这样，对面就能逼着你没法操作石子，再开一次箱子。如果每次开完箱子后异或和总是非 $0$ ，先手必败。 反之，若能开出一个异或和 $=0$ 的集合，就可以逼着对面开箱子了。 只需要在第一步开极大的异或和 $=0$ 的集合，后手就会沦为前面讲过的那种情况。 所以判别的方法就是 : 是否存在一个集合使得异或和为 $0$。使用线性基就可以了。 - $\bf Staircase$ 有 $n$ 层阶梯，编号 $1…n$，每层阶梯上有一些石子。 两个玩家轮流操作，每次操作可以将第 $j$ 层阶梯上若干(至少一个)石头放到 $j-1$ 层阶梯上，第 $0$ 层阶梯即为地板。 将最后一颗石头从阶梯移到地板上的玩家胜利。 不难发现，所有偶数阶梯都等价于垃圾桶。若一方尝试将偶数阶梯中的石子移出(至奇数阶梯)，下一个人只需要紧跟着把这些石子丢到下一个(偶数)阶梯即可，最终会到达地板。这个过程中，先后手是不会转换的。 接下来考虑奇数阶梯，一步就可以把任意多的石子丢进垃圾桶，实际上就等价于 $\rm Nim$ 问题。 **例题** : [P5363 [SDOI2019]移动金币](https://www.luogu.com.cn/problem/P5363) - $\bf Gra$ 有 $m(\leq 10^9)$ 个格子排成一行，从左到右编号 $1…m$ ，其中 $n(\leq 10^5)$ 个给定的格子里有硬币，且编号为 $m$ 的格子里没有硬币。 两人轮流操作，每次选择一个硬币，移动到它右边第一个不含石子的格子里。 将**某个**石硬币移动到编号为 $m$ 的格子的人胜利。 考虑将某个硬币移动到 $m$ 需要多少步，实际上就是该棋子右侧的空格数。 由此可以想到，将一枚硬币看做大小为 右侧空格数 的石子堆，每次可以拿掉一个，最早将某一堆拿空的人赢。 但是，事情并没有这么简单，当你移动某个棋子的时候，可能会填掉其他一些棋子右侧的一个空位。 手玩能够发现，这样的影响只会发生在“跳过”某一段棋子时。通过选择这一段中谁跳，可以使得大小为 $k$ 的**一部分**石子堆一起变为大小为 $k-1$ 的。 这其实很像下阶梯，我们再进行一步转化，可以把某一段硬币视作一个阶梯上的石子堆，就可以等效为 $\bf Staircase$。 - $\bf Take\ and\ Break$ - [P3185 [HNOI2007]分裂游戏](https://www.luogu.com.cn/problem/P3185) 有 $n$ 堆硬币 , 编号为 $0…n-1$。 两名玩家轮流取硬币 , 每一轮中 , 选取 $3$ 堆硬币 $i,j,k$ ( $i<j,j≤k$ ) 从 $i$ 中取出一枚，并向 $j,k$ 中各放入一枚 (如果 $j=k$ 则向 $k$ 中放入 $2$ 枚)。 不能按上述规则操作的人输。 若将每个位置的硬币堆看做一个子游戏,其两两之间会互相影响。 但是,若把每个硬币看做一个子游戏,不难发现这些游戏两两独立。 可以把在位置 $i$ 上的硬币看做一堆大小为 $m-i$ 的石子。 那么,操作的意义就是 : 选取一堆石子,并分裂成两堆比自己小的石子。 这样,就可以对单堆递推出 $SG$ 函数值了,复杂度是 $O(w^3)$。 [评测记录] () - [P5387 [Cnoi2019]人形演舞](https://www.luogu.com.cn/problem/P5387) | [Sol](https://www.luogu.com.cn/blog/command-block/post-shuo-xue-ji-lu-p5387-cnoi2019-ren-xing-yan-wu) - $\bf Lasker's\ Nim$ 每次可以从一堆中拿走若干石子，或者将一堆分裂成两个非空石堆。 此时每堆石子是独立的，可以单独分析。 对与状态 $[k]$ ,其后继状态可能是 $[0]...[k-1]$ ,也可以是 $[i]+[j]\ (i+j=k$ 且 $i,j>0)$ ，共 $O(k)$ 种。 若值域是 $w$ ，我们可以 $O(w^2)$ 递推出 $SG$ 函数值来。然后就做个 $\rm Nim$ 和。 - **一维翻硬币问题** $n$ 个硬币排成一行，有正有反，从左向右按 $1\sim n$ 编号。 按照某种规则选取硬币集合翻转，但是受到操作的**最右侧**的硬币必须从正面翻到反面(否则转移可能成环)。 注意到，两个完全相同的游戏在 $\rm SG$ 和中会互相抵消，故将反面朝上的硬币翻为正面朝上可以简单地视作多添加了一个同样的反面朝上的硬币而造成抵消。 - $\bf Turning\ Turtles$ 一维翻硬币问题。每次可以选择一枚或两枚硬币翻转，无法操作的玩家输。 可以等价于 $\rm Nim$ 游戏 : 第 $i$ 个位置的一个硬币等价于大小为 $i$ 的石子堆。 若单翻 $i$ 相当于取完一堆。 若翻 $i,j$ ，当 $j$ 从反面翻到正面时，相当于对某一堆取走了 $i-j$ 个石子。 当 $j$ 从正面翻到反面时，相当于同时删去了大小分别为 $i,j$ 的两堆。 我们能够发现， $\rm Nim$ 游戏中，若有两堆石子相同，则可以同时去掉,不会影响 $SG$ 和。 此处也就相当于增加一堆 $j$ 并与原来有的一个 $j$ 抵消，和拿去 $x-y$ 个石子是等效的。 - 一维翻硬币问题又一例 : [P4077 [SDOI2016]硬币游戏](https://www.luogu.com.cn/problem/P4077) | [Sol](https://www.luogu.com.cn/blogAdmin/article/edit/312820) - $\bf Mock\ Turtles$ 一维翻硬币问题。每次可以翻转一个、两个或三个硬币，最右边的硬币必须从正面翻到反面。 奥妙重重。 - $\bf Anti-SG$ 规则和上文中的公平组合游戏略有不同，规定得到终止态的玩家获胜（称之为“ $\text{Anti}$ 规则”）。 此时，两个游戏的和 $A+B$ 仍然会产生游戏二元组 $(A,B)$ ，定义其终止态为 $(A',B')$ ，当且仅当 $A',B'$ 分别是 $A,B$ 的终止态。 此时， $SG(A+B)$ 和 $SG(A),SG(B)$ 之间并没有简洁的关系。但是，仍然存在判断游戏多元组胜负的简便方法。 - **SJ 定理** : 设 $G_{1...m}$ 为游戏组合中的所有游戏，以 $\text{Anti}$ 规则进行，则先手必胜的充要条件为 : - $\bigoplus\limits_{i=1}^m SG(G_i)\neq 0$ 且 $\max\limits_{i=1}^m SG(G_i)>1$ - $\bigoplus\limits_{i=1}^m SG(G_i)= 0$ 且 $\max\limits_{i=1}^m SG(G_i)\leq1$ 两者之一成立。 **证明** : 考虑归纳并分类讨论。 1. $\bigoplus\limits_{i=1}^m SG(G_i)\neq 0$ 且 $\max\limits_{i=1}^m SG(G_i)>1\quad$ 应是 $\rm N$ 态。 2. $\bigoplus\limits_{i=1}^m SG(G_i)= 0$ 且 $\max\limits_{i=1}^m SG(G_i)\leq1\quad$ 应是 $\rm N$ 态。 3. $\bigoplus\limits_{i=1}^m SG(G_i)\neq 0$ 且 $\max\limits_{i=1}^m SG(G_i)\leq 1\quad$ 应是 $\rm P$ 态。 4. $\bigoplus\limits_{i=1}^m SG(G_i)= 0$ 且 $\max\limits_{i=1}^m SG(G_i)>1\quad$ 应是 $\rm P$ 态。 首先，终止态是 $\rm N$ 态，其也满足第二个条件。 1. 若只有一个 $SG(G_i)>1$ ，则将其操作为 $SG(G_i')=0$ 或 $1$ ，使满足条件 3。 若有多个 $SG(G_i)>1$，根据经典 $SG$ 理论，可以修改其中一个使得异或和变为 $0$ ，使满足条件 4。 2. 将任意一个 $SG(G_i)=1$ 变成 $SG(G_i')=0$ 即可满足条件 3。 3. 对于任意一个可操作的 $G_i$ 都有 $SG(G_i)=1$。这说明对于所有 $G_i\rightarrow G_i'$ ，都有 $SG(G_i')\neq 1$。 若 $SG(G_i)=0$ ，则满足条件 2。若 $SG(G_i)>1$ ，则满足条件 1。 4. 此时不可能只有一个 $SG(G_i)>1$ ，所以一次操作后仍有 $\max\limits_{i=1}^m SG(G_i)>1$。 根据经典 $SG$ 理论，一次操作后异或和必然非 $0$ ，则满足条件 1. - $\bf Misère\ Nim$ [P4279 [SHOI2008]小约翰的游戏](https://www.luogu.com.cn/problem/P4279) 规则同 $\rm Nim$ ，但是取得最后一个石子的人输。 直接套用 $\text{Anti-SG}$ 即可。 [评测记录](https://www.luogu.com.cn/record/47109181) - $\bf Nim_k$ 规则同 $\rm Nim$ ，但是每一轮可以同时操作 $1…k$ 个石堆。 此时，游戏之间并不是独立的，不能套用经典的 $SG$ 和。 观察普通 $\rm Nim$ ，若仅有两堆相同的石子，则后手总是可以模仿对方的决策，先手必败。 对应到 $SG$ 和，即异或值为 $0$。 在 $\rm Nim_k$ 中，若仅有 $k+1$ 堆相同的石子，后手总是可以在先手上一轮未操作的堆中模仿对方的决策，先手必败。 可以猜测 $\rm Nim_k$ 的规则与 $k+1$ 有一定关系。 - **Nim-k 定理** : 设 $A_{1...m}$ 为各堆石子数目。 将 $A_{1...m}$ 用二进制表示。将这些二进制数**直接看做** $k+1$ 进制数，然后做不进位加法。若结果为 $0$ 则先手必败，反之必胜。 形式化地，记 $A_i=\sum\limits_{j=0}g_{i,j}*2^j$，先手必败当且仅当 $\forall j,\sum_{i=1}^mg_{i,j}\bmod(k+1)=0$。 **证明** : 我们暂称上述 $k+1$ 进制不进位加法和为“特征值”。 考虑归纳，终止态的特征值显然为 $0$。 1. 特征值非 $0$ 需证能找到一个特征值为 $0$ 的后继。 考虑和 $\bmod (k+1)$ 不为 $0$ 的最高位，假设和为 $m(\leq k)$ 。 任意选出 $m$ 个在该位为 $1$ 的石子堆，并将其这一位置为 $0$ ，则之后可以随意设置。 考虑下一个和 $\bmod (k+1)$ 不为 $0$ 的位，假设和为 $r$。设之前选中的 $m$ 堆石子此时有 $a$ 个 $1$ ，$b$ 个 $0$。 分类讨论 : - ① $a\geq r$ ，在 $a$ 个 $1$ 中选 $r$ 个变为 $0$。 - ② $b\geq k+1-r$ ，在 $b$ 个 $0$ 中选出 $k+1-r$ 个变为 $1$。 - ③ $a<r,b<k+1-r$ ，考虑再征用 $r-a$ 个为 $1$ 的石子堆。 这样，操作的总堆数即为 $m+r-a=a+b+r-a=b+r<k+1-r+r=k+1$ ，合法。 将 $m$ 更新为 $m+r-a$。 2. 特征值为 $0$ 需证找不到一个特征值为 $0$ 的后继。 我们最多改变 $k$ 堆石子，故每一位上 $1$ 的数目变化量是 $[-k,k]$ 的。 现在问题是 : 将 若每一列的变化都为 $0$ ，则说明每一个 $0\rightarrow 1$ 都对应一个同位的 $1\rightarrow 0$。 但是，操作只能使得 $A$ 变小，所以某个 $0\rightarrow 1$ 一定在更高位有一个 $0\rightarrow 1$。 这样，最高位一定都是 $0\rightarrow 1$ ，矛盾。 注意， $\rm Nim_k$ 的结论并不能扩展到一般 $SG$ 函数。 - 例题 ： [P2490 [SDOI2011]黑白棋](https://www.luogu.com.cn/problem/P2490) | [Sol](https://www.luogu.com.cn/blog/command-block/post-shuo-xue-ji-lu-p2490-sdoi2011-hei-bai-qi) - $\bf Misère\ Nim_k$ 设石子数转二进制后视为 $k+1$ 进制做不进位加法得到的和为 $S$。 先手必胜当且仅当下列两条之一成立 : 1. 不存在 $>1$ 的石堆，且堆数 $\bmod(k+1)\neq 1$ 2. 存在 $>1$ 的石堆，且 $S\neq 0$ 证明略。 # $\bf SG$ **积** - **二维翻硬币问题** $n\times m$ 个硬币排成矩阵，有正有反，从左向右按 $[1\sim n,1\sim m]$ 编号。 按照某种规则选取硬币集合翻转，但是受到操作的**最右下侧**的硬币必须从正面翻到反面(否则转移可能成环)。 类似地，翻面操作可以看做新增一枚正面朝上的硬币。 - $\bf Acrostic\ Twins$ 二维翻硬币问题。每次操作可以翻转两枚硬币，两枚硬币要么同行，要么同列。 类似地，可以把一个硬币看做两堆大小分别为 $(x,y)$ 的石子，每次可以从任意一边进行上一个游戏的操作。 不难看出 $SG([x,y])=x{\ \rm xor\ }y$。 - $\bf Turning\ Corners$ & $\bf SG$ **积的定义** 二维翻硬币问题。是每次操作可以翻转某个矩形角上的四个硬币。 并不容易直接看出 $SG$ 函数来，考虑暴力打表观察。 设 $f[i,j]$ 为一个位置为 $[i,j]$ 的硬币的 $\rm SG$ 值。 有 $f[x,y]={\rm mex}\{f[a,b]{\ \rm xor\ }f[a,y]{\ \rm xor\ } f[x,b]:0\leq a<x,0\leq b<y\}$. （图表来自 @Owaski）  仍然没有发现? 那就对了……几分钟就能看出来的东西也太廉价了吧…… 本问题非常经典， $\rm SG$ 积的定义和该问题有极大的联系。 把 $SG(G_1+G_2)$ 记作 $G_1\oplus G_2$。 对自然数 $x,y$ ，定义 $\rm SG$ 积为 : $$x\otimes y={\rm mex}\{(a \otimes b)\oplus(a\otimes y)\oplus(x \otimes b):0\leq a<x,0\leq b<y\}$$ （即为 $f[x,y]$） - $\bf SG$ **积的计算** - 基本运算法则 不加证明地给出下列运算法则 : （It sounds amazing!） $$x\otimes y=y\otimes x$$ $$x\otimes (y\otimes z)=(x\otimes y)\otimes z$$ $$x\otimes (y\oplus z)=(x\otimes y)\oplus(x\otimes z)$$ 观察上表，还可以发现 $0\otimes x=0,\ 1\otimes x=x$。 根据这些法则，可以在计算 $x\otimes y$ 时进行一系列转化。 $$12\otimes 9=(8\oplus 4)\otimes (8\oplus 1)=(8\otimes 8)\oplus(8\otimes 1)\oplus(4\otimes 8)\oplus(4\otimes 1)$$ 然后查表，最终答案为 $13\oplus 8 \oplus 11 \oplus 4=10$。 一般步骤 : 先将 $x\otimes y$ 中 $x,y$ 二进制拆分，然后利用分配律展开，最后得到一系列 $2$ 的幂次的 $\rm SG$ 积。 这样，我们只需解决所有 $2$ 的幂次的 $\rm SG$ 积，之后查 $O(\log^2 x)$ 次表即可完成任意 $\rm SG$ 积的计算。 但是，打表的时间消耗仍然非常大。 - Fermat 2-power 经过数学家们的努(gao)力(shi)，我们现在有两个更加强大的运算法则 : 定义 Fermat 2-power 为形如 $2^{2^n},n\in N$ 的数，集合记为 $F_2$。 对于 $x\in F_2$ ，对于任意一个 $y<x$ ，有 $x\otimes y=x\times y$ ， $x\otimes x=\frac{3}{2}x$。 例 : $3\otimes 16=48,\ 4\otimes 4=6$。 现在我们能快速解决 $F_2$ 中数的 $\rm SG$ 积，但是非 $F_2$ 的 $2$ 的幂次仍然无法直接解决。 - 最终计算 当计算 $x\oplus y$ 且 $x$ 为 $2$ 的幂次时 ，设 $G(x,y)=x\otimes y$。 找到 $a$ 满足 $2^{2^a}\leq x< 2^{2^{a+1}}$ ，令 $M=2^{2a}$ 。 将 $x,y$ 表示成 $x=p\otimes M,y=(q\otimes M)\oplus t$。 （其中 $p=x/M$ ， $s$ 尽量小） $$ \begin{aligned} G(x,y) &=(p\otimes M)\otimes\big((q\otimes M)\oplus t\big)\\ &=(p\otimes q\otimes M\otimes M)\oplus(p\otimes t\otimes M)\\ &=\big(p\otimes q\otimes (M\oplus\tfrac{M}{2})\big)\oplus(p\otimes t\otimes M)\\ &=\big(p\otimes q\otimes (M\oplus\tfrac{M}{2})\big)\oplus(G(p,t)\otimes M)\\ &=\big(p\otimes q\otimes M)\oplus(p\otimes q\otimes\tfrac{M}{2}\big)\oplus(G(p,t)\otimes M)\\ &=\big(G(p,q)\otimes M)\oplus G(G(p,q),M/2)\oplus(G(p,t)\otimes M)\\ \end{aligned} $$ 这将 $G(x,y)$ 的计算转化成了 $G(p,q),G(G(p,q),M/2),G(p,t)$ 的计算。 设 $g(n)$ 为计算 $G(x,y)$ 且 $x,y\leq 2^{2^n}$ 时的复杂度。 则有 $g(n)=3g(n-1)$ 即 $g(n)=O(3^n)=O\big((\log x)^{\log_2^3}\big)\leq O(\log^2x)$。 由此，在 $O({\rm poly}(\log w))$ 的预处理之后，即可 $O(\log^2 w)$ 计算 $\rm SG$ 积。 - **游戏的积** 在能够快速计算 $\rm SG$ 积之后，我们随之解决了 $\text{Turning Corners}$ 问题。 $\rm SG$ 和与游戏的和紧密相连。而与 $\rm SG$ 积相伴的是另一个概念 : 游戏的积。 给定两个一维翻硬币游戏 $G_1,G_2$ ，定义 $G_1\times G_2$ 为一个二维翻硬币游戏，操作如下 : 若 $G_1$ 中翻转 $x_1,x_2\dots x_n$ 是一个合法操作，$G_2$ 中翻转 $y_1,y_2\dots y_n$ 是一个合法操作，那么在 $G_1\times G_2$ 中翻转 $(x_i,y_j),i\in[1,n],j\in[1,m]$ 是一个合法操作。 定义 $\text{Twin}$ 为每次必须要翻转两个硬币的一维硬币游戏。 可以发现，$\text{Turning Corners}$ 实质上是两个 $\text{Twin}$ 的积。 - **Tartan Theorem** 记 $g_1(x)$ 是编号为 $x$ 的硬币在 $G_1$ 中的 $\rm SG$ 函数，类似地有 $g_2(y)$。 在 $G_1\times G_2$ 中编号为 $[x,y]$ 的硬币的 $\rm SG$ 值即为 $g(x,y)=g_1(x)\otimes g_2(y)$。 比如，若硬币从 $0$ 开始标号，则在 $\text{Twin}$ 中 $g(x)=x$ ，则在 $\text{Turning Corners}$ 中 $g(x,y)=x\otimes y$。 前面我们分析出了若干个独立的游戏组合起来之后的 $\bf SG$ 函数值。 现在我们要研究把两个游戏**叠加**的结果。