博弈论

Bash游戏

$A$和$B$,有$n$颗石子,每次可以取$x$颗,其中$1 \leq x \leq m \\$,求$A$是否能赢.

考虑直接令石子数量为状态,有$SG ( x ) = mex \{ SG ( y ) | \max \{ 0 , x - m \} \leq y \leq x - 1 \} \\$,注意到$SG ( x ) = 0$当且仅当$x \equiv 0 ( \mod m + 1 )$.

我们使用数学归纳证明:

当$0 \leq x \leq m$时,显然成立.

而对于$x$,如果$x \equiv 0 ( \mod m + 1 ) \\$,那么集合$S = \{ y \in \mathbb{ Z } | \max \{ 0 , x - m \} \leq y \leq x - 1 \}$中一定$\nexists y$满足$y \equiv 0 ( \mod m + 1 ) \\$.

也就是$\nexists y$满足$SG ( y ) = 0$,那么$SG ( n ) = 0$.反之,一定存在.

Nim游戏

$A$和$B$,有$n$堆石子,第$i$堆石子有$x_i$个石子.每次可以任选一堆取走若干个石子,最后不能取的人输.求先手是否必胜.

注意到如果$x$均等于$0$一定先手必败.考虑令$w = x_1 \oplus x_2 \oplus . . . \oplus x_n$($w$即为全游戏的$SG$值),那么先手必败当且仅当$w = 0 \\$.

证明:

只需证明当$w \ne 0$时一定存在一种方法使得$w = 0 \\$.

考虑$w$的最高位为第$k$位,那么一定存在一个$x_i$的第$k$位为$1$.将它改为$0$,然后这个$x_i$的后面几位可以随意更改.

Example1(Nimk游戏)

$A$和$B$,有$n$堆石子,第$i$堆石子有$x_i$个石子.每次可以任选不超过$k$堆取走若干个石子,最后不能取的人输.

将$x_i$写成二进制,如果每一位的$1$的个数均是$k + 1$的倍数,那么先手一定必败.道理是差不多的.

Example2(Multi-Nim游戏)

Nim游戏,但是玩家每回合可以将任意一堆石子数量大于等于$2$的石子堆分成任意两堆不为空的石子堆.没法操作的人输.

本质仍然是SG游戏,我们正常做就行.

$SG ( x ) = mex \{ \{ SG ( v ) | x \rightarrow v \} , \{ SG ( x - i ) \oplus SG ( i ) | 1 \leq i < x \} \} \\$.

找一下规律可以发现:

$$\begin{aligned} SG ( x ) & = \begin{cases} x - 1 & x \equiv 0 ( \mod 4 ) \\ x & x \equiv 1 或 2 ( \mod 4 ) \\ x + 1 & x \equiv 3 ( \mod 4 ) \\ \end{cases} \\ \end{aligned}$$

不妨设当$x \leq 4 k$时结论成立.

当$x = 4 k + 1$时,前半部分一定是取遍了$[ 1 , 4 k ]$.

但是一定不存在$a$和$b$满足$a + b = 4 k + 1$并且$SG ( a ) \oplus SG ( b ) = 4 k + 1$.讨论一下$a$和$b$在$\mod 4$意义下的值就会发现不可能.

其他的是同理的.

SG游戏

$n$个DAG,每个DAG只有一个起始点,起始点上有一枚棋子.$A$和$B$每次可以选一个图,将上面的棋子沿DAG移动一条边,不能移动的人输.

直接使用$SG ( u ) = mex \{ SG ( v ) | u \rightarrow v \}$.

那么先手必败当且仅当所有DAG初始节点的SG异或起来是$0$.

首先如果$SG ( u ) = x$,那么$\forall 0 \leq y < x$,$\exists v$使得$u \rightarrow v$且$SG ( v ) = y$.可以发现这就如同Nim游戏了.

但是与Nim游戏不同的是,可能$\exists y > x$,但是仍然可以转移到.

但在这种情况下,我可以继续转移到一个$u ‘$使得$SG ( u ‘ ) = x$,因此异或值不变.

Example1(Anti-SG游戏)

SG游戏,但是不能取的人赢.

SJ定理:

先手必胜当且仅当下面两个条件满足一个:

1. 游戏的SG函数不为$0$且游戏中某个单一游戏的SG函数大于$1$.

2. 游戏的SG函数为$0$且游戏中没有单一游戏的SG函数大于$1$.

如果没有单一游戏的SG函数大于$1$,那么显然游戏的SG函数为$0$就赢了,否则就输了.

而如果SG函数为$0$且存在某个单一游戏的SG函数大于$1$,一定是输的.

因为这个情况下,后手先按照正常$SG$游戏压着先手,最后一定会剩两堆一样大于$1$的,无论你怎么选,对手都可以压着你.如果你把一堆全选了,此时对手就可以把另一堆剩下一个,这样就必输;如果你把这一堆选的只剩下一个,对手就可以把它那一堆全选了,这样就也是必输的.

Example2(Every-SG)

SG游戏,但是每次每个能移动的游戏都必须移动,不能移动任何游戏的人输.

对于每个子游戏,如果先手必胜,先手一定会尽可能多争取时间.

反之,先手一定会尽可能早结束游戏.

在$DAG$上dp的时候除了$SG$我们再加一维表示时间耗费,就可以dp了.

Example2.5(Every-SG)

n个游戏,每个游戏两堆石子,每次可以从大的那堆中取小的那堆石子大小的整数倍的石子.

直接套用Every-SG的做法就行.

Example3(Nim on tree)

一棵有根树两个人,每次可以挑一棵真子树删掉,不能操作者输.

结论:$SG ( u ) = \bigoplus_{ u \rightarrow v } ( SG ( v ) + 1 )$.

考虑归纳假设.如果$u$只有$v$一个儿子.那么要么将$v$子树全删,要么删一部分,有:

$$SG ( u ) = mex ( x | x = 0 \lor 0 \leq x - 1 < SG ( v ) ) = SG ( v ) + 1$$

而如果有多个儿子,则每个儿子都相当于是一个SG子游戏,异或起来即可.

另一种理解方式:考虑只有一个儿子的情况,那么相当于这个儿子的所有状态都向终止节点连了一条边,终止节点的$SG$为$0$,而显然$SG$图中的其它节点的$SG$均要$+ 1$.

Example4

$n$个有根仙人掌,保证所有的环与树的结构只有一个公共点(环只有一条连到环外的边).

两个人分别操作删边,与根不连通的边都被删掉.

结论:奇环$SG = 1$,偶环$SG = 0$.

这么考虑:边数为$k$的链的$SG$为$k$.

而拆开奇环后,你得到的两条链奇偶性一定相同,因而不可能得到$1$.偶环同理,不可能得到$0$.

Example5

无向图,每次删掉一条边以及与根节点不连通的部分,无法操作者输.

考虑Example2.

Fusion定理:将偶环替换成一个新点,奇环替换成一个新点连出去一条边,做边双.对于一个边双,$SG$值只和他边的奇偶性有关.证明大概和上面一样.

斐波那契博弈

一个数$N$,两个人轮流令他减去一个数,第一次不能减完,每次减的不能超过上一次的两倍.

不能操作者输.

结论为:当且仅当$N$是斐波那契数时,先手必败.

考虑归纳证明:

先证明当$N$是斐波那契数时必败,不妨假设$N = N_0 + N_1$,

考虑将$N$看成两堆,因为如果第一次取走了大于$N_1$颗石子,由于$N_0 \leq N_1 \\$,则后手第二步可以全取走,必败.

并且一开始先手一定要在$N_0$堆取石子,原因是如果取了大于$N_0$颗石子,由于$N = N_0 + N_1 \leq 3 N_0 \\$.这样下一步后手就可以全取完.

那么现在先手应该开始取$N_0$这一堆,如果在这一堆取的过程中,先手一直取得不超过$N_0$剩下的数,那么根据归纳假设,后手一定可以取走$N_0$堆的最后一个石子,此时局面变成了只剩$N_1$颗石子.只要此时先手不能一次取走$N_1$颗石子,先手就必败.而后手最后一步拿走石子最多会拿走$\frac{ 2 }{ 3 } N_0$的石子,但是,$\frac{ 4 }{ 3 } N_0 < N_1$,因此一定不可能.

否则,仍然是先手取走了$N_0$全部石子,又当了先手取$N_1$的石子.仍然是必败的.

齐肯多夫定理:任意一个正整数都可以被表示成若干不连续的斐波那契数之和.

设$N = \sum_{ i = 1 }^k f_{ p_i }$,其中$p_1 < p_2 < p_3 < . . . < p_k \\$,先手取走$f_{ p_1 } \\$.由于$2 f_{ p_1 } < f_{ p_2 }$,因此后手接下来无论如何不可能取得大于等于$f_{ p_2 } \\$,问题转化为一堆大小为$f_{ p_2 }$的石子,此时先手必败.因此原问题的先手必胜.

二分图博弈

给出一张二分图和起点$S$,$A$和$B$轮流操作,每次操作只能选与上一个被选的点相邻的点,且不能选已经选过的点.

考虑二分图的所有最大匹配,如果在所有的最大匹配的方案中都包含了起点$S$,那么先手必胜,否则先手必败.

证明:

如果所有匹配都包含$S$,那么$A$只需要每次走到一个和$S$匹配的点即可.$B$无论如何不可能走到一个不在最大匹配中的点,不然,我们将路径全部取反,就得到了一个最大匹配不变但不包含$S$的点,与假设不符.

而如果存在一个匹配不包含$S$,如果$A$仍然第一步走到一个和$S$匹配的点那么$B$一定能想办法走到一个不在当前$A$选择的最大匹配中的点而在一个不包含$S$的最大匹配中的点,于是$B$必胜.

Example1([2022qbxt国庆Day5]C)

显然,一个人敢抢金条当且仅当没有人敢抢他的金条.假设$dp_{ S , x } = 0 / 1$表示目前集合$S$中的所有人都已经离场了,而目前金条在$x$手中,金条会不会被抢.显然,如果$\exists y$满足$dp_{ S \cup \{ x \} , y } = 0$,也就是金条在$y$手里不会被抢,那$x$手中的金条必定会被抢.

将这个抢的过程看作二分图博弈中走到相邻的点的过程,于是这个问题等价于二分图博弈.也就是说,如果二分图博弈先手必胜,那么第一个拿到金条的人一定会被抢.

因此,我们需要找到所有与$S$匹配的可能出现在最大匹配中的边,对应编号最小的那个点,金条最后一定在他手里.(第一步这么走后,一定能构造出)

这个怎么构造呢,我们考虑先跑一遍dinic求最大匹配,然后做一遍tarjan缩点,然后如果$S$和$x$并未匹配,那么我们判断二者是否在一个强连通分量中,如果在,那他们可以被匹配.

至于判断$S$是否一定在其中,只需要先删去$S$,跑dinic,再在残联网络上加上$S$,判断是否有新的增广路.

树上博弈

Example1(zr[23省选10连 day1] Clashmas)

注意到删点对树形态的影响,考虑重心

1. $n$为奇数,重心为后手点.

注意到此时后手一定可以通过一些方式维持重心不变,因此后手必胜.

1. $n$为奇数,重心为先手点.

我们不妨设先手是A,后手是B.

考虑一个事实:对于这样一棵树,我们删着删着一定会出现一个时刻使得此时$n$为偶数,有两个重心(比如最后只剩下两个点的时刻),根据(4)和(5)的讨论,此时胜负已分.而且不难注意到此时A变为了实际上的后手.

根据(5),如果B掌控了任意一个重心,那A就输了.因此A必定要使当前局面的两个中心均为A的点.考虑原重心的所有儿子,它们有的是A点,有的是B点.由于树的重心的性质,树的重心的移动一定是一点一点挪的,也就是说第一次出现上面的局面的时候,两个重心必有一个是原重心,另一个是原重心的儿子,接下来A和B就要对于另一个重心能取到哪个儿子做争夺.我们不妨设A的点的集合为$S_A$,B的点的集合为$S_B$.以原重心为根建树,设其所有儿子组成的集合为$S_C$,不难发现A能胜利(也就是让两个重心全都属于他)当且仅当$\sum_{ u \in S_A \cap S_C } siz_u \geq \sum_{ u \in S_B \cap S_C } siz_u$.

原因很简单:A和B必然每次都会去杀属于对方的子树中$siz$最大的那棵.由于A有着先手优势,因此只要满足上面的条件,A总能获胜.

1. $n$为偶数,唯一重心,重心为后手点.

类似(2)的讨论,最后一定有某个时刻使得此时$n$为偶数,有两个重心(比如最后只剩下两个点的时刻),此时A仍然是先手,根据(5),只要他掌控一个重心就可以获胜.

类似地,不难发现胜利条件等价于(2).

1. $n$为偶数,两个重心,重心均为后手点.

注意到此时整棵树分为两个大小相等的部分,因此后手一定可以维持这个场面不动,后手必胜.

1. $n$为偶数,至少有一个重心是先手点.

注意到此时先手一定存在一种方式开局,使得重心仍为这个先手点,这样就转化为第一种情况,先手必胜.

散题

Problem1([CSP-S2020]贪吃蛇)

首先注意到,如果一个蛇吃完后还不是最小的蛇,那它一定会吃.因为被吃的蛇是单调不降的,而吃蛇的蛇是单调不增的,因此下一个蛇如果要吃,那一定会比它还小,所以至少会先被吃掉,而那条蛇会被吃掉,它就一定不会选,所以无论如何这条蛇都不会被吃掉.

我们考虑如果吃完后变成了最小的蛇后会怎么样,我们设$f_i$为还剩$i$条蛇的时候能不能吃,那$f_i = 1$的话,要么$i = 2$,要么吃完后不是最小的,要么$f_{ i - 1 } = 0$.

递归做就好了.另外这题需要复杂度$O ( n )$,需要用几个队列/双端队列维护.

Problem2([AGC023D]Go Home)

首先,最后一个人要么是最左边的,要么是最右边的.而显然这两边中人数较少的一个将会是最后一个到家的,那么这个人的目标就是帮助另一边的人尽可能快到家,于是会帮着它投票.以此类推不断递归下去.

Problem3(牛客38727E)

首先考虑如果有人作为第$n - p + 1$个人复读了,那接下来复读一定不会被惩罚,于是没复读的都会复读,这样这个人就必死.于是最多只会复读$n - p$个人.

继续思考,如果有人作为第$n - 2 p + 1$个人复读了会怎么样,后面的人也都不会被惩罚了,于是也会继续复读.

以此类推,会发现最后只会有$n \mod p$个人复读,并且一定是前$n \mod p$在一轮内复读完.

Problem4(arc155D)

考虑直接转移,但是有可能出现在原地转的情况,注意到这种情况我们只需要记录$f_{ i , j }$表示当前的$G$是$i$,$G$的倍数还剩下$j$个,然后做转移,再进一步发现我们只关心$j$的奇偶性.于是记$f_{ i , 0 / 1 }$即可.

这题给我最大的启示是,我们不能假定让双方共同遵守一个”君子协定”,博弈论最重要的就是博弈,不能说我们最后再选倍数之类的,他的转移路线会变化的.

Problem5

给一个“日”字型图,七条边,每条边有一堆石子.每次可以选任意多条不构成环的边,然后将这些边上的石子堆取走任意多个石子.求先手必胜策略,以及如果每条边的石子数量在$[ l_i , r_i ]$,那么有多少种先手必胜的情况.

考虑将这个图分成三部分,上面三条边,中间一条边,下面三条边.那么这三部分一定不能全选至少两部分,不然会构成环.反之一定构不成环.

先手必败当且仅当,这三部分内部的边上石子均相等,并且所有边异或值为$0$.

否则,考虑将上部分和下部分三条边先全改成相等的,会修改较大的两条边.

接下来,我们剩了三条边,我们只能选择改其中一条,使得他们仨异或值为$0$.

换句话说,我们现在有$x_1 , x_2 , x_3$,我们要将其中一个$x_i$改为$y_i$,其他不变,使得他们仨异或值为$0$.和Nim游戏类似,假设他们仨异或值的最高位为$k$.那么一定有一个$x_i$的第$k$位为$1$,将它改为$0$,后面就可以随意变换.

思路具体怎么想到的呢,可以发现整个图只有三个环,并且这三个环都可以由这几部分组成.接下来就可以每个部分的$[ l_i , r_i ]$求个交,用FWT做一遍异或卷积.数位dp也可以做.

Problem6

Nim游戏,但是每堆石子有一个$K_i$.如果这堆石子剩$x_i$个每次最多取$\lfloor \frac{ x_i }{ K_i } \rfloor$个石子.求先手是否必胜.

结论是

SG(n-\lfloor\frac n k\rfloor,k)&n\ne 0(\mod k)\\

\frac n k&n=0(\mod k)\\

\end{cases}\\

考虑数学归纳就可以证明.

然后我们就只需要对于$k$是否大于$\sqrt{ n }$讨论一下,如果$k < \sqrt{ n }$暴力,最多只会做$\sqrt{ n }$次.否则,意识到此时可以通过求一个区间$[ l , r ]$,满足$\forall x \in [ l , r ] , \lfloor \frac{ x }{ k } \rfloor$均相等,加速一下.这种区间最多只会有$\sqrt{ n }$个.

Problem7

一个数$N$,两个人轮流令他减去一个数,第一次不能减完,每次减的不能超过上一次.不能操作者输.

先手必败当且仅当$N = 2^k$,不然,每次选lowbit即可.

Problem8

A和B,有$n$颗石子,每次可以取$x$颗,其中$1 \leq x \leq \lceil \frac{ n }{ 2 } \rceil \\$.

仍然令石子数量为状态,注意到$SG ( x ) = 0$当且仅当$x + 1 = 2^k - 1$,也即$x = 2^k - 2 \\$.首先,注意到:

$$\begin{aligned} n - \lceil \frac{ n }{ 2 } \rceil & = \lfloor \frac{ n }{ 2 } \rfloor \\ SG ( n ) & = mex \{ SG ( y ) | \lfloor \frac{ n }{ 2 } \rfloor \leq y \leq n - 1 \} \\ \end{aligned}$$

设$n = 2^k - w$,其中:

$$\begin{aligned} - 2^{ k - 1 } + 2 & \leq w \leq 2 \\ \lfloor \frac{ 2^k - w }{ 2 } \rfloor & = 2^{ k - 1 } - \lfloor \frac{ w }{ 2 } \rfloor \\ \end{aligned}$$

当$w = 2$时,原式$= 2^{ k - 1 } - 1 > 2^{ k - 1 } - 2 \\$.反之.$2^k - 2 \leq$原式.因此数学归纳即可证明.