NFLS 博弈杂记

Nim 游戏

$n$ 堆石子，每次选一堆拿走正整数个，无法操作者输。

结论是 $\bigoplus_{i} a_i=0$ 则先手必败否则先手必胜， $\oplus$ 表示按位异或。

证明：若 $\bigoplus_{i} a_i=0$ ，则下一步必定无法转移到 $\bigoplus_{i} a_i=0$ 的状态（必须取走正整数个），要么已经没有石子，要么只能转移到 $\bigoplus_{i} a_i>0$ 的状态，而 $\bigoplus_{i} a_i>0$ 的状态总可以转移到 $\bigoplus_{i} a_i=0$ 的状态，方法是取出最高位与 $\bigoplus_{i} a_i$ 相同的 $a_k$ ，令其下一步转移到 $a_k\oplus\bigoplus_{i} a_i$ ，根据异或的消去律这是成立的。

公平组合游戏 - SG定理

公平组合游戏的定义需要在有向无环图上。

每个人可以把点挪到一个后继，每个人都完整的知道这张图，至于是否公平并不重要（只需要把操作者也视为一个维度即可）。

定义一个状态（图上的一个点）的 $\rm SG$ 值为出点 $\rm SG$ 值的 $\rm mex$ （最小的未出现的非负整数）， $s_x=0\iff$ 该局面先手必败。

公平组合游戏：每次可以任选一个子游戏中操作一步，不能操作的人输。

放到图上就是有多个棋子，每次将一个棋子挪到它的后继。

$\rm SG$ 定理：公平组合游戏的 $\rm SG$ 值等于每个子游戏的 $\rm SG$ 值的按位异或和。

以下常用 $s_i$ 表示 $\text{SG}(a_i)$ ，也即第 $i$ 个状态的 $\rm SG$ 值。

证明类似 $\rm Nim$ 游戏，首先数学归纳假设后继状态都满足该定义，设 $s_x$ 为 $\bigoplus_{i} s_i$ ，假设我们要走到 $g(g<s_x)$ ，把 $g\oplus s_x$ 的最高位拿出来，必定可以找到 $i$ 使得 $h(s_i)=h(g\oplus s_x)$ ，我们令第 $i$ 个游戏转移到 $s_i'=s_i\oplus g\oplus s_x$ ，则新的 $s_x=g$ ，也就是说我们总可以转移到比 $\bigoplus_{i} s_i$ 小的状态，但显然转移不到与 $\bigoplus_{i} s_i$ 相等的状态（每个点的所有后继与该点必然不同），于是得证。

在实际应用中，我们几乎可以将一个 $s_x=k$ 的状态视为一个大小为 $k$ 的石子堆，唯一的区别是有人可以将石子堆的大小变大（但不能不变），若该定理成立则显然赢家没有理由将其变大，维持原状即可获得胜利，若输家将其变大，那赢家可以在下一步抛给输家一个 $\rm SG$ 值相同的局面。

巴什博弈

$n$ 堆石子，每次选一堆拿走 $[1,k]$ 个，无法操作者输。

观察建出的图， $s_x=x\bmod (k+1)$ ，使用 $\rm SG$ 定理解决即可。

阶梯博弈

$n$ 堆石子，每次选一堆把正整数个拿到前面那一堆，第一堆直接拿走，无法操作者输。

我们断言，阶梯博弈等价于对所有奇数位置做 $\rm Nim$ 游戏，也就是先手必败当且仅当 $\bigoplus_ia_{2i-1}=0$ 。

若该定理成立，那么赢家显然只会动奇数上的位置，唯一的问题是输家可能会动偶数上的位置，这样赢家就可以把输家移动的那些石子再次往前挪一格，丢给输家一个所有奇数位置上都和原来一样的局面。

阶梯博弈可以扩展到所有二分有向无环图的情况，只需要确定每个点是奇数层还是偶数层即可。

阶梯博弈可以与巴什博弈结合，结论是一致的。

反 Nim 游戏 - Anti-SG

对于公平组合游戏，我们修改获胜条件为不能操作者赢得游戏。

结论：则 $\exist i,s_i>1$ 时， $\bigoplus_i s_i>0\iff$ 先手必胜，否则 $2\mid \sum_is_i\iff$ 先手必胜。

首先假设 $\rm SG$ 变大不会影响局面，如果输家将其变大赢家可以将其变回去，现在将 $\rm SG$ 看作石子。

首先 $\forall i,s_i\le1$ 时是显然正确的，因为石子只能一个一个取，所以我们只关注 $\exist i,s_i>1$ 。

对于 $\bigoplus_i s_i>0$ 的局面，如果有不少于两个 $i$ 满足 $s_i>1$ ，则根据 $\rm Nim$ 游戏的分析显然可以动其中一个使得 $\exist i,s_i>1$ 且 $\bigoplus_i s_i=0$ ，否则只有一个 $s_i>1$ 的，那我们可以根据目前场上 $1$ 的奇偶性来选择将其变为 $1$ 还是 $0$ 以保证自己必胜。

Every-SG

对于公平组合游戏，我们修改规则为每次需要同时将所有没有结束的子游戏进行一步，不能操作者输。

显然每个游戏仍然是独立的，且赢家想要尽量慢的赢，输家想要尽量快的输，赢家一定不会求死，因为无论该游戏能否挺到最后只要自己赢那自己一定不亏。

于是在求必赢必输时顺便求出每个状态的时间即可，无须求 $\rm SG$ 值。

BZOJ 4147 Euclidean Nim

两人玩游戏，有一个石子堆此时大小为 $n$ ，若为 $A$ 操作，若 $n<p$ 则他只能向其中加入 $p$ 颗石子，否则可以拿走任意 $kp$ 颗石子（ $k$ 为非负整数），若为 $B$ 操作则把 $p$ 换成 $q$ 规则一样，无法操作者输。

判断谁会获胜，或永远进行下去。

$T\le 10^6,1\le p,q,n\le 10^9$ 。

首先永远不会结束当且仅当 $\gcd(p,q)\nmid n$ 。

首先不妨假设 $n\ge p$ ，如果不满足则模拟不超过两轮使得 $n\ge$ 先手的权值。

若 $p\le q$ ，则先手必胜，因为先手总可以让 $n\gets n\bmod p$ ，然后后手只能加，这样根据裴蜀定理一定会结束。

否则如果 $n\bmod p\ge q$ 则先手必败，因为无论先手怎么操作第一轮，攻守之势异也，变为上面的情况。

否则必定有 $n\bmod p<q<p\le n$ ，先手只能选择令 $n\gets n\bmod p$ ，否则就满足了 $q\le p\le n$ 且 $q$ 先手， $p$ 必败。

若 $n\bmod p+q<p$ 则先手必败，若 $n\bmod p+q=p$ 则先手必胜，否则递归到 $(n,p,q)\gets (n\bmod p+q,p,q)$ 。

容易发现 $n$ 从第一轮往后就不可能超过 $2p$ ，一直在 $(p,2p)$ 之间变化，那么 $\bmod\ p$ 的本质其实就是 $-p$ ，也就是每次 $n\gets n-p+q$ ，若 $n$ 变为 $0$ 则先手必胜，也就是 $(p-q)\mid n\bmod p$ 则先手必胜，否则先手必败。

BZOJ 3895 取石子

$n$ 堆石子，每次可以选一堆石子取走一个，或合并两个非空堆。

不能操作的人输。

$\sum n\le 10^6,a_i\le 10^9$ ，

$\forall a_i>1$ 时， $n-1+\sum a_i$ 为奇数时先手必胜，当输家创造一个大小 $=1$ 的堆时，赢家总可以及时将它合并走。

这启发我们那些 $a_i>1$ 的堆总是会被需要它们被合并的人及时合并掉，并且不想它们被合并的人无法阻止这一点，所以它们可以看作一个 $\max(0,\sum_i[a_i>1]-1+\sum_i[a_i>1]a_i)$ 个石子的堆。

设 $f_{i,j}$ 表示当前局面有 $i$ 个大小为 $1$ 的石子堆，还有一个大小为 $j$ 的石子堆，先手是否必胜。

可以破坏一个大小为 $1$ 的石子堆，变为 $f_{i-1,j}$ 。

可以取走 $j$ 中的一个石子堆，变为 $f_{i,j-1}$ 。

可以合并一个 $1$ 和 $j$ ，变为 $f_{i-1,j+1}$ 。

可以合并两个 $1$ ，变为 $f_{i-2,j+3-[j=0]}$ 。

然后打表找规律，可以做到线性。

BZOJ 3759 Hungergame

有 $n$ 个箱子，第 $i$ 个箱子里有 $a_i$ 颗石子，初始都关闭，Alice 和 Bob 都知道 $a_{i=1}^n$ ，每轮每个人可以将至少一个未打开的箱子打开，或在所有打开的一个箱子中拿走至少一颗石子。

无法操作的人输。

$\sum n\le 10^6,a_i\le 10^9$ 。

首先 $a_i=0$ 时相当于一堆大小为 $n$ 的石子，若初始 $\bigoplus_{i=1}^na_i=0$ 那么先手可以全打开然后玩 $\rm Nim$ ，于是先手必胜。

进一步地，我们猜测，只要有一个子集 $S$ 满足 $\bigoplus_{i\in S} a_i=0$ 那么先手必胜。

首先先手可以把 极大的 异或和为 $0$ 的箱子集合打开，那么无论后手如何操作，打开的箱子异或和总 $>0$ ，于是先手总是可以把它归零。

不存在的情况同理，判断可以用线性基。

HDU 3032 Nim or not Nim?

每次要么把当前石子分成非空两堆，要么取正整数颗。

$\sum n\le 10^6$ 。

先拆 $\rm SG$ ，然后打表即可。

HDU 3595 GG and MM

有 $n$ 个石子堆对，每次需要把每个能操作的对进行操作：选择正整数 $k$ ， $a'\gets a-kb$ 或者 $b'\gets b-ka$ ，两个变量都不能取到负数，有一个变量操作前是 $0$ 视为无法操作。

一轮中谁也无法操作的人输。

$\sum n\le 10^6,a_i\le 10^9$ 。

显然外面是一个 Every-SG，里面是一个欧几里得过程，若当前层只有一颗显然只能取一颗，否则如果下面那层先手必胜就取的剩一颗，否则全取完。