博弈论一些结论

## k倍减法游戏 有⼀个整数$S\ge 2$，先⾏者在S上减掉⼀个数x，⾄少是1，但⼩于S。之后双⽅轮流把S减掉⼀个正整数，但都不能超过先前⼀回合对⽅减掉的数的k倍，减到0的⼀⽅获胜。 考虑构造一个数列 满足数列上的数都必败 记为$a$ 另一个序列为$b$ 表示$a_1$到$a_i$可以表示出的最大数(比$a_{i+1}$小的) 那么有转移 $$ a_{i+1}=b_{i}+1 $$ $$ b_{i+1}=a_{i+1}+b_{j} $$ 其中$j$为满足$a_j\times k <a_{i+1}$的最大数 ## SG函数 没啥可说的 就是后继状态的$mex$ 注意多个独立游戏的和为$sg$的异或 ## N阶Nim游戏 就是每次可以选择$N$堆石子 每堆减少任意多个 其它不变 有结论 后手必胜当且仅当在每一个二进制位上 所有数这一位为1的个数是$N+1$的倍数 否则先手必胜 ## 阶梯Nim 就是奇数段的异或和是否为0 ## 翻硬币游戏 特征是翻的最右边的硬币一定是从正面翻到反面 有结论每个硬币独立 那么就是每个硬币的$sg$的异或和 例如每次只能翻连续不超过三个硬币 那么 $$ sg_i=mex(0,sg_{i-1},sg_{i-1}xor\ sg_{i-2}) $$ 可以找规律 ## 砍树游戏 一棵树 每次删掉一条边以及它的子树 不能操作的人输 有结论$x$节点的$sg$值等于所有儿子的$sg$值$+1$的异或和 ## Anti-SG游戏 即不能操作的人赢 则先⼿必胜当且仅当： • （1）游戏的SG函数不为0且游戏中某个单⼀游戏的SG函数 ⼤于1。 • （2）游戏的SG函数为0且游戏中没有单⼀游戏的SG函数⼤ 于1。 ## Nim积 我们对于一些二维$Nim$ 游戏 可以拆分成两维单独的 $Nim$然后求 $Nim$ 积。 定义为 $$ x⊗y=mex{(a⊗b)⊕(a⊗y)⊕(x⊗b),0≤a<x,0≤b<y} $$ 其中 $⊗$ 定义为 $Nim$ 积，⊕ 定义为异或。 由于$nim$积有分配律 我们可以把两个数的积拆成一些$2$的整数次幂之和的积 考虑求$2$的整数次幂的$nim$积 $2$的整数次幂又可以拆成一些$2^{2^k}$ 之积 那么对于两个相同的$2^{2^k}$ 它们的积等于$\frac{3}{2}\times 2^{2^k}$ 还有结论$2^{2^k}$和任意一个比它小的数的$nim$积等于它们之积 那么可以记忆化$O(log^2n)$解决 具体实现时两个函数互相调用 第一个求$2$的整数次幂中合并两个$2^{2^k}$的答案时要用到第二个也就是算任意整数的$nim$积的函数 这东西的应用 比如说二维的翻硬币游戏 两个边长只能分别从两个集合中选取 那么分别先求出一个点行的$sg$值和列的$sg$值 最后的值就是它们的$nim$积