博弈问题

Published: by Creative Commons Licence

  • Tags:

动态规划解决博弈问题

博弈问题是指有两个玩家参与，每个玩家轮流做出决策，最后按照结果判断两个玩家的胜负情况。

如果一个游戏先手必胜，我们称该游戏处于N-position，否则后手必胜，我们称游戏处于P-position。

比如我们可以设计这样一个问题，有一组数，记做$a_1,a_2,\ldots,a_n$，数的总和为奇数。玩家A与B先后轮流决策，每次决策，该名玩家必须从数集中取走最左或最右的数，并从数集中删除。当数取完时，取得的数总和较大的胜利。问两个玩家都做最优决策时，哪个玩家会胜利。

这个问题，就是一个经典的博弈问题，我们可以用动态规划枚举所有可能的状态解决。记$dp(l,r)$表示当数集为$a_l,a_{l+1},\ldots,a_r$时，如果游戏是N-position，记为1，否则为P-position，记为0，可以很容易推出公式：$dp(l,r)=\max(1-dp(l+1,r),1-dp(l,r-1))$。

通过上面的动态规划我们就能以$O(n^2)$的时间复杂度解决博弈问题。如果我们将每个$dp$值视作一个结点，并从$dp(l+1,r)$和$dp(l,r-1)$中向$dp(l,r)$连接一条单向边，就可以构造一幅有向无环图。这幅图，可以清晰展示整个决策流程。

实际上，上面这个博弈问题，有非常简单的解决方案，那就是先手必胜，因为先手可以决定自己选择奇下标的数还是偶下标的数，因此必胜。可以看出虽然动态规划很强大，但是如果能直接给出有用的性质，可以大幅优化时间复杂度。

决策不一定是非胜即负的，比如考虑井字游戏，A持白子，B持黑子，每次可以在一个3*3表格中的一个空白格子中落子，如果三个白子连成一条直线，则A胜利，游戏结束，如果三个黑子连成一条直线，则B胜利。

很显然，如果双方都最优决策，那么游戏一定是平局的。在上面的这幅图中，这意味着有一部分结点代表着平局，平局的结点仅有向平局和胜利结点的边。

决策图不一定是无环的，比如这样一个游戏。如果A和B各持有两个整数，整数大小为0~9。二人轮流出牌，当A出牌时，将其中一张牌$x$换成$(x+y)%10$，其中y是上次B出的牌（默认A和B之前出的牌为0），对于B同理，只是y是A上次出的牌。当两个玩家手中持有的牌有一张换成0时，就认为该名玩家获得胜利。

很显然还是能通过状态压缩后建立图来解决。但是图中存在环，因此我们需要利用Bellman-Ford算法的松弛技术来完成。而一个结点如果在松弛完后，状态还是无法确定，那么这个结点一定代表平局。

Nim游戏和Sprague–Grundy函数

用动态规划解决博弈问题，很容易遇到瓶颈，比如状态数过多，无法逐一计算。

考虑Nim游戏，有$n$堆石头，第i堆石头有$a_i$个石头。玩家A、B轮流出手，每次出手，玩家必须选择一堆石头，并从中取走至少一个（最多可以全取）。如果无法完成操作，则认为玩家失败。

很显然，我们可以用动态规划，共$\prod_{i=1}^na_i$种状态，如果有100堆石头，每堆有100个石头，那么状态数将达到$100^{100}$，这显然是无法完成的。

这时候估计大家现在开始纷纷开脑洞，猜测每堆奇偶性会影响胜负等等。

下面说一下正确的解题姿势。

我们之前定义的动态规划函数的值仅为1和0，实际上我们抛弃了很多有用的信息，现在我们把它们加回来。首先所有堆石子为0的结点值为0，保持不变。但是对于其它结点$u$，我们记所有从它出发沿单向边移动一步可以抵达的结点集合为$v_1,v_2,\ldots,v_m$，记$sg(u)=\mathrm{mex}(sg(v_1), sg(v_2), \ldots, sg(v_m))$。其中sg为Sprague–Grundy函数。而$\mathrm{mex}$函数值为不同于所有参数的最小非负整数，比如$\mathrm{mex}(1,2)=0$，$\mathrm{mex}(0,2)=1$。

我们这里提到的Nim游戏，现在可以转换为另外一个问题，我们将每一堆都视作图中的一个棋子，每位玩家都可以选择任意一个棋子沿着有向边移动一步，如果所有棋子都无法移动，那么该名玩家失败。

下面我们讨论两个命题。

命题1：如果仅一枚棋子，那么游戏处于P-position当且仅当该棋子所在结点的sg值为0

证明：对于代表失败结果的结点，该棋子没有外向边，sg值显然为0。对于sg值为0的棋子，其所有相连的结点sg值肯定非0，因此其只能移动到N-position，即该结点必定为P-position。而对于sg值非0的棋子，其一定与某个sg值为0的结点相连，因此移动到该结点，游戏进入P-position，因此该结点对应的是N-position。这里证明不是非常严谨，可以换成归纳法进行证明。

命题2：如果有n个独立棋子，那么游戏处于P-position当且仅当所有棋子所在的sg值的异或和为0

证明：如果所有棋子都处在代表失败结果的结点，那么它们的sg值异或和自然是$0$。如果异或和为$0$，那么移动一枚棋子，记其原来的sg值为$a$，后来的sg值为$b$，必定有$a\neq b$，故此时异或和一定为$a\oplus b \neq 0$，因此N-position之后一定是P-position。而如果异或和$s$不为0，那么我们一定能找到一个棋子，其所处结点的sg值为$x$，满足x包含s中二进制的最高位，我们将该棋子从所在结点移动到sg值为$s\oplus x < x$的后继结点上，这时候异或和为$s\oplus x\oplus x\oplus x=0$，因此我们在N-position后一定能移动到P-position。配合归纳法可以证明。

这样我们就可以将从n堆石头中移除石头看做为n个独立游戏，而我们只要建立n堆石头各自的决策图，并计算棋子所在结点的sg值的异或和就可以判断游戏的状态了。但是由于Nim游戏中每个独立游戏拥有相同的决策图，因此我们可以复用，事实上，这里我们连决策图都不用建立，剩余n个石子对应的结点的sg值一定是n。

我们考虑到我们仅仅利用了决策图的sg值，与决策图具体代表的游戏是无关的。因此我们可以同时玩多个游戏，只需要利用sg函数就可以快速计算游戏所处的状态。比如我们将Nim游戏稍加变形，操作第i堆石头一次性必须移除1~i个石头。我们可以将每一堆石头建立独立的决策图，并计算每个结点的sg值。之后异或所有决策图上棋子的sg值，为0，则游戏处于P-position，否则处于N-position。

棋子分裂

我们稍微修改一下游戏。我们每次并不能移动棋子，但是可以选择一枚棋子，将其分裂为若干颗新的棋子，每个棋子落在特殊的结点上，保证若干步后游戏一定会结束。

这时候我们可以修改每个结点的sg值。在结点$u$上，假设有$k$种分裂策略，第i种分裂策略分裂后棋子分别落在$v_i^1,v_i^2,\ldots$。那么我们定义$sg(u)=\mathrm{mex}(v_1^1\oplus v_1^2\oplus \ldots, \ldots, v_k^1\oplus v_k^2\oplus \ldots)$。

稍微修改命题2的证明可以很容易证明游戏处于P-position当且仅当所有棋子所在sg值的异或和为0。

Nim-k博弈

Nim游戏是Nim-k游戏的一个子集。Nim-k游戏定义为，有n堆石头，每堆分别有$a_1,a_2,\ldots,a_n$个石头，两个玩家A、B轮流执行下面操作：

选择1~k个堆，并从这k个堆中各移除若干个石头（不同的堆允许移除不同数量的石子，至少一个）。

如果一个玩家不能执行操作，则认为失败。A先手，B后手，问谁胜利。

对于我们之前的讨论的Nim游戏可以认为是Nim-k中k为1时的特殊情况。之前已经证明过了Nim游戏处于P-position当且仅当每堆石头石子数的异或和为0。这里我们直接给出Nim-k游戏的胜利条件，Nim-k游戏处于P-position当且仅当对于所有i，One(i)为$k+1$的倍数，其中One(i)表示$a_1,a_2,\ldots,a_n$中二进制第i位为1的数值个数。

很显然对于失败态，此时所有One(i)均为0，因此处于P-position。

对于某个P-position，对于任意一次操作后，我们记$j$为本次操作修改的最高比特位。由于是最高位，因此第$j$位的修改一定是$1\rightarrow 0$。$1\rightarrow 0$转移至少发生1次，最多发生k次，而由于初始时$One(j)=0\pmod{k+1}$，因此修改后$One'(j)$一定不能整除$k+1$。即P-position转移后一定是N-position。

对于某个N-position，我们可以构造一种取法，使得下一个状态为P-position。我们维护一个集合（初始时为空），并不断向其中加入石堆。

  1. 找到一个最大的值j，使得$r=One(j)\pmod{m+1}\neq 0$。如果不存在则算法终止，否则进入第2步。
  2. 设集合中石头堆中第j位为1的有a个，为0的有b个。那么如果$r\leq a$，我们从中选择r个石头堆将第j比特从1改为0，之后回到第1步。否则进入第3步。
  3. 如果$r+b\geq (m+1)$，则我们从中选择$m+1-r$个堆，将第j比特从0改为1，之后回到第1步。否则进入第4步。
  4. 我们取$r-a$个第j比特位1的石头堆加入集合，并将r个石头堆将第j比特从1改为0。这样我们就将第j比特修正为$k+1$的倍数。此时集合的大小为$r-a+a+b=r+b< m+1$，因此是合法的。$=

Nim-k游戏虽然类似于Nim游戏，但是不能保证对于一般的决策图也能满足这样的性质。即允许同时操作1~k个棋子在决策图上移动一步，不能保证每个对于每个比特i，$One(i)$均为0就能保证是P-position。考虑这样一个游戏，共4堆石头，数量为1，1，1，2，每次允许选择1~2个石头堆，并移除一个石子。这样4个石头堆对应的SG函数分别为1，1，1，0。因此满足$One(0)=3$能整除$2+1$，因此我们有理由认为这是一个P-position，但是实际上这是一个N-position，因为我们可以将局势改变为0，1，1，1。

斐波那契博弈

有n个石头，A、B轮流出手，每次至少拿一个石头，最多拿对手上一次取的数目的两倍。第一次取的人不能全取。问先手胜还是后手。

直接给答案，如果n是斐波那契数的一项，则游戏是P-position，否则是N-position。

先说点斐波那契数列的性质。

性质1：$\frac{3}{2}F_i<F_{i+1}<2F_i$

性质2：$F_{i+2}\geq 2F_i$

性质3：任意正整数都可以表示为若干个不连续的斐波那契数列项的和

对于0，0是斐波那契数列的第0项，因此是P-position。

下面我们通过归纳法证明，假设对于小于n的斐波那契项都是P-position。如果n是斐波那契数列的一项，我们可以得出n是前两项a、b的和，即a+b=n。则我们选择的一定小于a，否则对手会一次性将剩余的一起取走。由于归纳法，我们得知在经过若干轮交手后，B完成一次操作，使得取走的石子总数为a，留下的石子数为b。考虑B最后一次取的数量，至少为1，最多为$\frac{2}{3}a$。这样A之后最多取$\frac{4}{3}a<b$，即相当于我们在b上玩游戏，且A先手取，不能完全取尽。由归纳法知最后能取尽b的一定是B。因此B一定胜利，游戏处于P-position。

如果n不是斐波那契的任意项，我们可以将其展开为$f_1,f_2,\ldots,f_k$，满足两两不连续，且$f_1<f_2<\ldots,f_k$。A第一次取$f_1$个石子，而之后变成b不能先手取，之后我们能保证A能取到第$f_1,f_1+f_2,\ldots,n$个石子。

对偶博弈

n个石子，围成一个环。A、B轮流出手，每次可以取连续的一段石子，长度为1~k。不能完成操作的认为失败，问谁胜利。

当k为1的时候，每个玩家每次只能取走一个石子，因此游戏的胜负仅于n的奇偶性有关。

当k大于1时，若$n\leq k$，则A一次性能取完，A胜利。

当k大于1且$n>k$时，无论A第一次怎么取，设剩下m个连续石子，B可以通过一次操作，将石子分成两个等长连续段。之后无论A在哪个部分操作，B在另外部分同步操作，就能保证取走最后一个石子，获得胜利。

威佐夫博弈

有两堆石子，分别有n、m个石子。A、B轮流出手，每次可以从一堆取任意石头，或从两堆石子中取相同数量石头。问谁胜利。

不妨设$n\leq m$，游戏处于N-position当且仅当，存在一个k，使得$n=\lfloor Wk \rfloor$且$m=\lfloor (W+1)k\rfloor$，其中$W=\frac{1+\sqrt{5}}{2}$。

记$L(i)=\lfloor Wi \rfloor$，记$R(i)=\lfloor (W+1)i\rfloor$，有$L(N)\cap R(N)=\emptyset$和$L(N)\cup R(N)=N$。

两队列取值问题

有两个队列，每个队列包含一个非负值序列。给定一个阈值m（m不超过两个队列中所有元素之和），我们维护一个值sum，表示已经从两个队列中取出的数值的总和。

现在有两个人A、B。他们每次需要执行下面一个操作：

从两个队列中任选一个非空队列，从队列中弹出头部数值。

如果某个人完成一次操作后，sum值达到m，那么就判定他输，另外一个人赢。

这个问题的解法非常有趣。设队列1的长度为W，队列2的长度H，我们可以绘制一个H+1行W+1列的网格。第i行j列表示队列1已经弹出i个元素，队列2弹出j个元素，接下来操作的人是否会获胜。如果能获胜，我们将网格涂上白色，否则涂上黑色。同理对于无效网格（即执行完这些操作sum已经超出阈值），我们默认它们都是白色。

我们需要证明一些非常有用的命题：

命题1：任意两个黑色网格不会相邻

命题2：如果网格(a,b)是白色的，那么(a+1,b+1)也是白色网格。

证明：

如果(a+1,b+1)是无效网格，命题显然，之后仅考虑(a+1,b+1)是有效网格的情况。证明非常简单，如果网格(a+1,b+1)是有效网格，那么(a,b+1)和(a+1,b)一定也是有效网格。由(a,b)是白色可以推出(a,b+1)和(a+1,b)至少有一个是黑色网格，同理可以推出(a+1,b+1)一定是白色网格。

命题3：如果网格(a+1,b+1)是黑色的，那么(a,b)也是黑色的

证明：

由于(a+1,b+1)是黑色的，因此(a+1,b)和(a,b+1)都一定是白色的，由此可以得知(a,b)是黑色的。

命题4：如果(a+1,b+1)是有效网格，那么网格(a,b)和网格(a+1,b+1)一定同色，

证明：

根据命题2和命题3，我们只需要考虑不存在(a,b)是黑色的，而(a+1,b+1)是白色的情况。

考虑到(a,b)是黑色的，因此(a,b+1),(a+1,b)一定都是白色的有效网格。而考虑到(a+1,b+1)也是白色的，因此(a,b+2),(a+2,b)则一定是黑色的网格。

而由于(a+1,b+1)是白色的有效网格，因此(a+2,b+1),(a+1,b+2)至少一个是黑色网格。而再考虑到(a,b+2),(a+2,b)一定是黑色的网格，这与命题1相悖。因此命题得证。

因此我们希望得知网格(0,0)的颜色，只需要去查询(1,1)的颜色。因此我们实际上需要计算点 \((0,0),(1,1),\ldots,(\min\{H,W\},\min\{H,W\})\) 的颜色。总的时间复杂度为 \(O(\min\{H,W\})\)

提供一道问题。

约瑟夫环

约瑟夫环的问题如下：

有n个人围成一圈，我们顺时针将人标记为0，1，…，n-1。从标记为0的人开始沿着顺时针报号（1，2，3等），谁报到k，就会被杀死。之后从被杀死的人后一个人继续重新开始报号。

在这样的一个游戏中，有若干个问题非常有趣：

问题1：第i个死亡的人是谁。

问题2：编号为j的人是第几个死亡的。

先考虑问题1，可以很容易推出一个递推算法，记$f(n,i)$表示剩余n个人的时候，第i个死亡的是谁。$g(n,j)$表示在只剩下n个人的时候，第j个人在第几个回合死去。

得出下面递推公式：

\[f(n,i)=(f(n-1,i-1)+k) \% n\\ g(n,j)=g(n-1,(j-k)\%n)+1\]

利用这些递推公式，我们可以在$O(n)$的时间复杂度内回答以上问题。

但是可以发现$f(n-1,i-1)+k$大部分时候都会不超过n，因此我们可以直接多步合并执行来优化函数$f$，同理$j-k$大部分时候也都不会小于0，因此可以同样进行优化。

优化后两个函数的时间复杂度应该为$O(min(n, k\ln\frac{n}{k}))$。

取反游戏

考虑有这样一个序列$a_1,a_2,\ldots, a_n$，A和B两个人用这个序列玩一个游戏，A先手，游戏步骤为：

取一个数值$i$，要求$a_i>0$，之后将$a_{i}$减去1，并且可以选择$i$后面的任意多个有效下标$I={i+1,i+2,\ldots}$，$I$可以为空集，对于任意$j\in I$，将$a_j$加上1。一旦有人不能再操作，那么这个人就输去比赛，问先手胜还是后手胜。

很容易发现这个问题和奇偶性有关，我们可以将问题重新描述为：

取一个下标$i$，要求$a_i$为奇数，选择任意多个有效下标$I={i,i+1,i+2,\ldots}$，对于任意$j\in I$，改变$a_j$的奇偶性。一旦有人面对全是偶数的情况，那么这个人就输去比赛，问先手胜还是后手胜。

由于奇偶性问题和数值大小是没有任何关系的，因此我们可以认为$a_i$都足够大，大到能支撑到游戏分出胜负为止。

这个问题还是很难解决，我们可以建立一个新的序列$b_i$，用于描述$a_i$，如果$a_i$与$a_{i-1}$的奇偶性不同，那么$b_i$为1，否则$b_i$为0。这样之前的问题中的区间$[l,r)$的翻转操作，可以用序列${b_i}$中位于$l$处的1移动到$r$处来描述。

取一个下标$i$，要求$b_i$为1，选择某个下标$j$，满足$i<j\leq n$，将位于$i$处的$1$移动$j+1$处。一旦面临$b_1,\ldots, b_n$都是0的情况，那么这个人就输去比赛，问先手胜还是后手胜。

考虑位于$i$处的1，移动1，相当于取石子游戏，它的$SG$函数值应该为$n+1-i$。而序列${b_i}$中的多个1，可以理解为多个独立的NIM游戏。

这边的证明是依赖于直觉的，暂时没有想到严谨的证明。

Nimber的加法和乘法

定义$\mathrm{mex}(S)$表示$\min(N/S)$，即$S$中未出现的最小的自然数。其中$\mathrm{mex}$的意思是minimum excludant。

Nimber的加法定义为：

\[a\oplus b=\mathrm{mex}(\left\{a'\oplus b:a'\lt a\right\}\cup \left\{a\oplus b':b'\lt b\right\})\]

其值与$a$和$b$二进制的亦或和相同。

Nimber的乘法运算定义为：

\[a\otimes b=\mathrm{mex}(\{(a'\otimes b)\oplus (a\otimes b')\oplus (a'\otimes b'): a'<a,b'<b\})\]

可以Nimber的加法运算符合封闭性，满足结合律和交换律，且加法单位元为$0$，每个数的逆元为自身，因此Nimber构成了一个加法群。

可以发现：

  • $a\otimes 0=0$
  • $a\otimes b=b\otimes a$
  • $a\otimes 1=a$
  • $(a\otimes b)\otimes c=a\otimes (b\otimes c)$
  • $(a\oplus b)\otimes c=(a\otimes c)\oplus (b\otimes c)$

即乘法运算也满足结合性，分配律，交换律等，存在单位元$1$，故Nimber构成了一个交换环。

要计算Nimber乘积，我们需要一些更加强力的性质:

对于任意$x,y<2^{2^a}$

  • $x\otimes 2^{2^a}=x\cdot 2^{2^a}$
  • $x\otimes y<2^{2^a}$
  • $2^{2^a}\otimes 2^{2^a}=\frac{3}{2}2^{2^a}$

利用这些性质我们可以设计一个递归算法，$O(\log_2a\log_2b)$求解$a\otimes b$。具体可以参照参考资料中《从“k倍动态减法游戏”出发探究一类组合游戏问题》这篇文章。

SG定理：设若干个棋子的SG函数值为$SG(x_1),\ldots,SG(x_n)$，则这些棋子共同的SG值为$SG(x_1)\oplus \ldots \oplus SG(x_n)$。

Tartan定理：记若干个游戏$G_1,\ldots,G_n$的积为$G(V,E)=G_1\cdot \ldots \cdot G_n$，其中$V=V_1\times \ldots \times V_N$（笛卡尔积），$E={(x,y)|(x_i,y_i)\in E_i}$，其中$x=(x_1,\ldots,x_n)$，$y=(y_1,\ldots,y_n)$。那么棋子$x=(x_1,\ldots,x_n)$的SG值为$SG(x_1)\otimes\ldots \otimes SG(x_n)$

我们可以这样理解。

  • 如果有一个游戏，无法操作的时候玩家失败。则我们知道游戏的SG函数值决定了先手还是后手必胜，如果SG函数值为$0$，则先手必败，否则先手必胜。
  • 如果同时有$n$个游戏在进行，博弈双方每次只能选择一个游戏操作，只有当所有游戏都不能操作的时候玩家才失败，则游戏的SG函数值可以通过各个单独的函数的SG值的Nimber和得到。
  • 如果同时有$n$个游戏在进行，博弈双方每次需要同时选择所有游戏操作，只有不能操作的玩家才失败，则游戏的SG函数值可以通过各个单独的函数的SG值的Nimber积得到。

问题1：我们有一个$n\times m$矩阵$A$，每个网格中都有一盏灯，灯或开或关。现在要求两人进行博弈，轮流操作，每次操作都需要选择一个矩形（长宽均至少为2），且矩阵的右下角的灯必须为开状态，操作完成后，矩阵的四角的灯的状态发生改变（由开变关或由关变开）。无法操作的人视作失败。问先手还是后手必胜。一开始总共有$k$盏灯开着，告诉你它的坐标。这里$1\leq n,m\leq 10^{18},0\leq k\leq 10^5$。

发现单一维度下就是一个普通的NIM游戏，因此我们将行游戏和列游戏计算笛卡尔积就可以得出这个游戏。故$SG(x,y)=x\otimes y$。

一道原题。把这个问题扩展到三维空间题目。

这里顺带一提，允许退化的情况（即高度和宽度允许为1），这时候我们在左边和上边额外加一列一行，行号和列号均为0，且这一行一列的SG函数值均为0即可。这时候比如对于高度退化的情况下，我们可以认为矩阵的上部正好匹配了最顶上的那一行。于是乎我们吧原先的行列编号全部加1，就可以复用解法了。

问题2：有$n$个堆，第$i$个堆有$a_i$个石头，两人轮流操作，每次操作需要选择一个堆，拿走至少1个，最多$m$个石头，求先手还是后手必胜。这里$1\leq a_i\leq 10^9$，$1\leq n\leq 10^5$，$1\leq m\leq 10^3$。

由于不同堆的规则是相同的，因此我们可以只处理一次SG函数。同时可以发现SG的函数应该满足$SG(x)=SG(x+m+1)$（周期性）。因此我们可以只需要算出$SG(i)$，其中$i\leq m$。

问题3：有一行灯（第一个灯的编号为$0$），每个灯的状态为$0,1$，对应关灯和开灯状态。之后每次你可以选择某个非空子序列，要求前缀最靠右的灯一定处于开状态。要求将整个子序列中的灯的状态进行转换。现在两人轮流进行操作，不能操作的人为输家。问先手还是后手必胜。

这个游戏是Ruler游戏。第$i$盏灯的SG函数值为$SG(i)=lowbit(i+1)$，即$i$二进制形式中的最低一位$1$。具体证明不会。

问题4：有一行灯（第一个灯的编号为$0$），每个灯的状态为$0,1$，对应关灯和开灯状态。之后每次你可以选择长度不超过$k$的子序列，要求子序列z最靠右的的灯一定处于开状态。要求将整个子序列中的灯的状态进行转换。现在两人轮流进行操作，不能操作的人为输家。问先手还是后手必胜。

这道题，与问题3有点类似，只是为3没有长度约束。打表可以发现，对于$k$，其约束与$highbit(k)$是相同的（从$k$减少到$highbit(k)$不会影响最终的胜负）。同时会发现SG函数的周期正好为$highbit(k)$的因数，而前$highbit(k)$个灯的SG函数与没有约束的情况下是相同的，即普通的Ruler博弈。

利用取模，我们对于位于$x$的灯，我们可以推出$SG(x)=lowbit((x\pmod{highbit(k)) + 1})$。

问题5：我们有一个$n\times m$矩阵$A$，每个网格中都有一盏灯，灯或开或关。现在要求两人进行博弈，轮流操作，每次操作都需要选择一个矩形（长宽均至少为2，宽度不能超过$W$，高度不能超过$H$），且矩阵的右下角的灯必须为开状态，操作完成后，矩阵的四角的灯的状态发生改变（由开变关或由关变开）。无法操作的人视作失败。问先手还是后手必胜。一开始总共有$k$盏灯开着，告诉你它的坐标。这里$1\leq n,m\leq 10^{18},0\leq k\leq 10^5$。

可以发现行游戏和列游戏都是问题4，我们可以将其进行笛卡尔积得到问题5。而合并后的游戏可以用Nimber积求解。

提供一道题目:SRM748 Rectoggle。

Anti-Nim

Anti-Nim的问题描述和Nim游戏基本相同，除了拿走最后一个石子的人认为是输家。

命题：给定$n$个游戏，双方轮流操作，每次操作可以操作一个游戏。当所有游戏的SG函数值均为$0$的时候认为最后一次操作的人失败。那么先手仅在$3$种情况下必胜：

  1. 每个游戏的SG函数值均为$0,1$，且这些游戏的SG函数值亦或和为$0$。
  2. 存在正好一个游戏的SG函数值大于$1$。
  3. 存在多于一个游戏的SG函数值大于$1$，且这些游戏的SG函数值亦或和大于$0$。

证明：

首先我们可以忽略状态为$0$的单个游戏，因为如果一方将其变成非$0$，那么另外一方可以将其重新变回$0$。同样我们也不考虑SG函数值从$1$变到更大的情况，因为一方将其变大，另一方一定可以将其还原。

第一个条件如果成立，那么必胜是很显然的，因此不讨论。

当第二个条件成立的时候，如果有偶数个游戏的SG函数值为1，则我们将那么SG函数值大于$1$的游戏转换为$1$，否则转换为$0$，因此这样就进入了第一个条件下先手必败的状态。

现在仅考虑存在多于一个游戏的SG函数值大于$1$的情况。如果$SG$函数值为非$0$，先手可以将其转换为$0$，而后手只能将其转换为非$0$。同时可以发现后手操作时，面对的都是所有游戏SG函数值的亦或和为$0$的情况，因此此时至少有两个游戏的SG函数值大于$1$，不可能进入条件$2$逃离。

两端取值问题

题目1：给定一个长度为$n$的序列$a_1,\ldots,a_n$。之后两人轮流操作，每个人在自己的回合可以从队列头部或尾部弹出一个数值（弹出后这个数值就从队列中删除）。如果序列为空则游戏结束。在游戏结束后，如果一方弹出的数的总和比另外一方大，则获得胜利。保证$a_1+\ldots+a_n$是奇数（即不会出现平局）。问先手必胜还是后手必胜。其中$2\leq n\leq 10^5$，且$n$是偶数。

先手必胜，因为先手可以决定自己拿走所有奇数下标的数还是偶数下标的数。

题目2：给定一个长度为$n$的序列$a_1,\ldots,a_n$。之后两人轮流操作，每个人在自己的回合可以从队列头部或尾部弹出一个数值（弹出后这个数值就从队列中删除）。如果序列只剩下一个元素时游戏结束。先手方希望让剩下的元素尽可能大，而后手方希望让剩下的元素尽可能小，两者都是最优决策。问最后剩下的数为多大。其中$1\leq n\leq 10^6$。

考虑先手面对偶数的情况。可以发现先手一定可以取到$\max(x_{n/2},x_{n/2+1})$，因此这是结果的一个下界。而后手只要做与先手相反的操作（先手弹出头部，则后手弹出尾部），就可以保证最终剩下的数是$x_{n/2},x_{n/2+1}$中的一个（这显然对于后手是最优的，即最终值正好等于下界）。因此这时候结果一定是$\max(x_{n/2},x_{n/2+1})$。

可以发现对于后手面的偶数的情况下，最终结果为$\min(x_{n/2},x_{n/2+1})$，证明方式类似。

再考虑先手面对奇数的情况。我们知道如果我们选择弹出头部，则最终结果为$\min(x_{(n+1)/2},x_{(n+1)/2+1})$，对应的如果我们选择弹出尾部，则结果为$\min(x_{(n-1)/2},x_{(n-1)/2+1})$。而由于先手希望结果尽可能大，因此答案为$\max(\min(x_{(n+1)/2},x_{(n+1)/2+1}),\min(x_{(n-1)/2},x_{(n-1)/2+1}))$。

一道题目。

有向无环图上的博弈

有向无环图上的博弈，可以发现出现的最大sg函数值是$\min(V,\sqrt{E})$。

题目1：给定一个$n$个顶点$m$条边的有向无环图。之后不断重复以下操作：随机生成一个$1$到$n+1$的随机整数$v$，如果这个$v$不超过$n$，则在顶点$v$上加入一个棋子。如果$v=n+1$，则结束操作，进入比赛。比赛流程非常简单，两人轮流操作，每次沿着一条有向边移动一枚棋子。谁不能移动了就算失败。问先手获胜的概率是多少。其中$1\leq n,m\leq 10^5$

提供一道题目。

预先算出所有顶点的sg函数值。可以发现值的范围是$\sqrt{E}$之内。之后建立期望矩阵，$x_i$表示比赛开始前游戏的$sg$函数为$i$的期望次数，只后高斯消元即可，时间复杂度为$O(E^{1.5})$。

Nim游戏的一些变种

考虑有多个Nim游戏。两个玩家A、B轮流操作，A先手。操作的人会选择其中一个未结束（可以继续操作）的Nim游戏，并做一些操作，使游戏的状态变更。

一般的情况下，如果某个玩家面对的所有游戏都结束的时候，那么他就是输家。我们可以通过为每个Nim游戏的结束态的sg函数设置为0，并将所有Nim游戏的sg函数值异或起来。如果异或和为0，那么先手必败，否则先手必胜。

现在我们稍微修改一下分出胜负的条件。

  1. 如果任意一个Nim游戏结束的时候，最后操作的人为赢家。
  2. 如果任意一个Nim游戏结束的时候，最后操作的人为输家。

当然我们必须保证所有Nim游戏初始的时候不处于结束状态。

现在我们需要判断是A获胜还是B获胜。

我们考虑任意一个游戏，我们加入新的状态：预备态。对于条件1的情况下，一个状态是必败态，当且仅当这个状态可以通过一步将游戏结束；而对于条件2，只有游戏结束的状态才是必败态。必败态的含义是在这个状态上进行操作的玩家会获胜。

可以发现无论在哪种情况下，当前操作的玩家一定不会允许游戏进入必败态。换言之，所有会导致游戏切换到必败态的操作都是被禁止的。可以发现此时如果一个状态，它只能转移到必败态，那么它的sg函数值为$0$，否则它的sg函数值为所有可进入状态的sg函数值的mex值。

之后对于对个游戏存在的情况，我们可以将这些游戏的sg值异或起来，记结果为$x$。A获胜的条件是：至少一个游戏为必败态或者$x\neq 0$。

不覆盖子串

考虑这样一个问题，有长度为$n$的一个01序列。现在由A和B轮流操作。操作人每次选择一段连续的仅包含0的非空子串删除，当无法操作时，当前操作人为输家。

现在要求判断先手必胜还是必败。

我们实际上可以把每段连续的0看成一个单独的游戏，每次我们删除子串，对应的就是将一个游戏分裂为两个子游戏（可能存在空游戏）。

我们可以发现每个单独游戏的状态仅由串长度所决定，对于长度为$k$的串，记它的sg值为$sg(k)$。

下面我们证明$sg(k)=k$。当$k=0$的时候，显然。现在可以发现状态$(k)$可以转移为$(0),(1),\ldots,(k-1)$，因此$sg(k)\geq k$。接下来我们考虑$(k)$分裂为两个子游戏的情况$(a),(b)$的情况，此时有$a+b<k$。由于$sg(a)=a$且$sg(b)=b$，因此$sg(a)\oplus sg(b)\leq a+b<k$，故我们有$sg(k)=k$。

提供一些题目:

参考资料