我发现自己挖坑的速度堪比挖坟速度。
又开新坑了。。。。

Nim 博弈

Nim游戏是公平组合游戏。（大意就是在任意一时间点，互换游戏双方对其游戏本身没有影响）。

  • 两名选手。
  • 两名选手轮流行动，每一次行动可以在有限合法操作集合中选择一个。
  • 游戏的任何一种可能的局面(position)，合法操作集合只取决于这个局面本身，不取决于轮到哪名选手操作、以前的任何操作、骰子的点数或者其它因素；局面的改变称为“移动”(move)。
  • 如果轮到某名选手移动，且此时无法进行移动，则这名选手负。

而局面共分为两种：

  1. P-position 先手必输。
  2. N-position 先手必胜。

取石子
$A_i$ 表示第 $i$ 堆的石子数。
假如一个局面为P-position $\Leftrightarrow$ $A_1\ xor\ A_2\ xor \ \cdots \ \ xor\ A_n=0$

证明,我们考虑数学归纳

  1. 假如$\forall i\in [1,n] A_i=0$ , 一定是P-position

  2. 若不是，则设$x=A_1\ xor\ A_2\ xor \ \cdots \ \ xor\ A_n (x\not ={0})$
    那么此时，设 $x$ 的二进制下最高位为第 $k$ 位。
    由于异或的本身性质，$\exists i\in [1,n]$ 使得$A_i$ 的第 $k$ 位为1。
    有结论:$A_i\ \ xor\ k<A_i$
    下面给出证明：由于 $k$ 是 x的最高位，所以 $k$ 位以上的不用管，只考虑 $k$ 位以下的
    原先的 $A_i$ 的第 $k$ 位为1，异或后为 0 显然小了。
    所以我们可以把 $A_i$ 这堆取成 $A_i\ \ xor\ x$。
    此时 $A_1\ xor\ A_2\ xor \ \cdots \ (A_i\ \ xor\ x)\ \cdots\ \ xor\ A_n=x\ \ xor\ x=0$
    所以根据归纳假设，移动后的局面为 P-position，故此时为 N-position

    特别的，若 $x=0$ 那么我们无论如何也找不出一个 $A_i$ 使的，其改变后 $A_1\ xor\ A_2\ xor \ \cdots \ (A_i’)\ \cdots\ \ xor\ A_n=0$
    充分性，必要性都证明完了。
    先写到这吧。

SG函数

SG函数用来解决一些复杂的Nim问题
我们先定义从状态x可以到达的状态y为x的一个后继
然后 SG(x)=mex{SG(y)|y是x的后继}
mex是什么？
$mex{a}$ (a是一个集合) 表示为最小的非负整数x不属于a。
Eg:mex{0,3,5}=1,mex{0,1,2,3,4}=5;
SG函数代表什么呢？
如果SG(x)=0表示必输,其余的即为必胜

所以为什么现在的SG函数可以解决Nim问题,也就是P-position,N-position局面
我们在分析N position,P position 局面的本质：
若为空集,则必为P position
存在 可以到达的状态必为P position,那他一定是N position
对于任意可到达的状态均为N position,那他一定是P position

那么我们考虑SG(x)的本质:
SG(x)=mex{a},若a为空集则SG(x)=0
若SG(x)$\not ={0}$ ,则 $\exists SG(y)=0$
若SG(x)=0,则 $\forall SG(y)\not ={0}$

是不是发现了SG 函数其实对应了N/P position 局面

这种对应其实也说明了，可以像N/P position 局面一样拆成若干子问题，然后求异或和。

总结，我们在做Nim的题时，重要的不是求出SG而是找到x->y这种的后继关系。
因为这种后继关系本质是构造了一个DAG，而DAG我们可以dp，而dp才是重要的！！