博弈
博弈在OI中大概是解决两个人玩一个游戏，在两个人都采用最优策略的情况下，当前局面是必胜还是必败。
博弈大概分以下几种解决方法：
找出必胜策略，DFS或者DP直接求，SG函数
找出必胜策略
这种方法并不常见。
例1：
有一堆石子有$n$个，每次可以拿$1$个或者$2$个，不能拿就输了。问先手必胜还是必败。
解：如果$n mod 3=0$必败，否则必胜。因为当$n mod 3=0$时，后手只需要在先手拿完之后保持$n mod 3=0$即可。当然不等于$3$时，先手可以直接让其变为等于$3$，则必胜。
DFS或者DP直接求
首先在博弈里面有两种状态，必胜态和必败态。因为两个人都是采用了最优策略，所以有以下定理:
结论
1.如果当前状态的后继状态有必败态，那么这一定是必胜态
2.如果当前状态的后继状态都是必胜态，那么这一定是必败态
例1：
有一堆石子有$n$个，对于一个集合$S={a[i]|i\in[1,n]}$，可以拿随意的$x\in S$个，不能拿就输了，问初始局面先手必胜还是必败。
解：设$f[i]$为当前还有$i$个石子的时候的时候是先手必胜还是必败。
首先边界条件是$f[0]=0$
显然根据上面的结论有
$$f[i]=
\begin{cases}
1,\exists \forall f[i-a[i]]=0\\
0,else
\end{cases}
$$
那么直接枚举计算即可。
也可以使用记忆化搜索来解决。
这种方法一般都作为博弈的暴力解法来出现，只能拿到部分分，但可以用来对拍。
SG函数
解决组合游戏问题通常都可以用这种方法进行转化。先来看一个问题
NIM游戏
有若干堆石子，每堆石子的数量都是有限的，合法的移动是“选择一堆石子并拿走若干颗（不能不拿）”，如果轮到某个人时所有的石子堆都已经被拿空了，则判负（因为他此刻没有任何合法的移动）。
解：
NIM和就是把每堆都看成单独的游戏，N堆的结果是每堆结果的异或和。
下列证明经转载（有耐心可以看一下，或者可以直接跳过，记住上面的结论就可以了）：
定义：P-position和N-position，其中P代表Previous，N代表Next。直观的说，上一次move的人有必胜策略的局面是P- position，也就是“后手可保证必胜”或者“先手必败”，现在轮到move的人有必胜策略的局面是N-position，也就是“先手可保证必胜 ”。更严谨的定义是：
1.无法进行任何移动的局面（也就是terminal position）是P-position；
2.可以移动到P-position的局面是N-position；3.所有移动都导致N-position 的局面是P-position。
按照这个定义，如果局面不可能重现，或者说positions的集合可以进行拓扑排序，那么每个position或者是P-position或者是N-position，而且可以通过定义计算出来。
以 Nim游戏为例来进行一下计算。比如说我刚才说当只有两堆石子且两堆石子数量相等时后手有必胜策略，也就是这是一个P-position，下面我们依靠定 义证明一下(3,3)是一个P是一个P是一个P-position。
首先(3,3)的子局面（也就是通过合法移动可以导致的局面）有(0,3)(1,3) (2,3)（显然交换石子堆的位置不影响其性质，所以把(x,y)和(y,x)看成同一种局面），只需要计算出这三种局面的性质就可以了。 (0,3)的子局面有(0,0)、(0,1)、(0,2)，其中(0,0)显然是P-position，所以(0,3)是N-position（只要找到 一个是P-position的子局面就能说明是N-position）。(1,3)的后继中(1,1)是P-position（因为(1,1)的唯一子局 面(0,1)是N-position），所以(1,3)也是N-position。
同样可以证明(2,3)是N-position。所以(3,3)的所有 子局面都是N-position，它就是P-position。通过一点简单的数学归纳，可以严格的证明“有两堆石子时的局面是P-position当且 仅当这两堆石子的数目相等”。
根据上面这个过程，可以得到一个递归的算法——对于当前的局面，递归计算它的所有子局面的性质，如果存在某 个子局面是P-position，那么向这个子局面的移动就是必胜策略。当然，可能你已经敏锐地看出有大量的重叠子问题，所以可以用DP或者记忆化搜索的 方法以提高效率（简单的博弈问题想到这一步就可以了）。但问题是，利用这个算法，对于某个Nim游戏的局面(a1,a2,…,an)来说，要想判断它 的性质以及找出必胜策略，需要计算$O(a1×a2×…×an)$个局面的性质，不管怎样记忆化都无法降低这个时间复杂度。所以我们需要更高效的判断 Nim游戏的局面的性质的方法。
直接说结论好了。
(Bouton’s Theorem)对于一个Nim游戏的局面(a1,a2,…,an)，它是P-position当且仅当a1^a2^…^an=0，其中^表示异 或(xor)运算。怎么样，是不是很神奇？我看到它的时候也觉得很神奇，完全没有道理的和异或运算扯上了关系。但这个定理的证明却也不复杂，基本上就是按 照两种position的证明来的。
根据定义，证明一种判断position的性质的方法的正确性，只需证明三个命题：
1、这个判断将所有terminal position判为P-position
2、根据这个判断被判为N-position的局面一定可以移动到某个P-position；
3、根据这个判 断被判为P-position的局面无法移动到某个P-position。
第一个命题显然，terminal position只有一个，就是全0，异或仍然是0。
第二个命题，对于某个局面(a1,a2,…,an)，若a1^a2^…^an!=0，一定存在某个合法的移动，将ai改变成ai’后满足 a1^a2^…^ai’^…^an=0。
不妨设a1^a2^…^an=k，则一定存在某个ai，它的二进制表示在k的最高位上是1（否则k的 最高位那个1是怎么得到的）。这时ai^k < ai一定成立。则我们可以将ai改变成ai’=ai^k，此时 a1^a2^…^ai’^…^an=a1^a2^…^an^k=0。
第三个命题，对于某个局面 (a1,a2,…,an)，若a1^a2^…^an=0，一定不存在某个合法的移动，将ai改变成ai’后满足 a1^a2^…^ai’^…^an=0。
因为异或运算满足消去率，由a1^a2^…^an=a1^a2^…^ai’^…^an可以得 到ai=ai’。所以将ai改变成ai’不是一个合法的移动。证毕。
根据这个定理，我们可以在O(n)的时间内判断一个Nim的局面的性质，且如果它是N-position，也可以在O(n)的时间内找到所有的必胜策略。Nim问题就这样基本上完美的解决了。
SG函数
SG函数是子状态SG值从0开始最小的没有出现的值，如果没有子状态自然SG是0，是必败态。
当且仅当SG(x)=0,x状态为必败态
SG定理
一个组合游戏问题的结论相当于其子游戏的NIM和。
为什么是对的呢。
根据SG函数的定义，如果SG(x)=k，那么x状态可以转移到$SG(S)=[0,k-1]$中的集合S中的任意一个状态。相当于NIM中每一堆石子可以转移到$[0,k-1]$中任意一个。所以可以根据相同的方法证明。
例：
有$k$堆石子，对于一个集合$S={a[i]|i\in[1,n]}$，可以从一堆石子中拿随意的$x\in S$个，不能拿就输了，问初始局面先手必胜还是必败。
解：
如果我们进行$k$维次DP的话，时间复杂度无法接受，为$O(a[1]a[2]a[3]…a[n])$。
考虑直接计算SG值，用一个集合来维护，递归解决。
|
|
时间复杂度$O(nk)$