阶梯nim

参考博客

问题：

有n个位置1...n，每个位置上有ai个石子。有两个人轮流操作。操作步骤是：挑选1...n中任一一个存在石子的位置i，将至少1个石子移动至i−1位置（也就是最后所有石子都堆在在0这个位置）。谁不能操作谁输。
求先手必胜还是必败。

结论

和nim问题很相似，却又不一样
因为这个是移动到下一位而非拿走
先说结论：
求位置为奇数的ai的异或和
如果异或和为0则先手必败
否则先手必胜

证明：

拿走某一堆石子的一部分，相当于将某个奇位置的石子移动到它左边的偶位置上。
如果大家都只动奇位置的石子，那么这等价于两人在玩Nim游戏。
但如果有人想打破规则呢？
　　假设Nim游戏先手必胜，那么先手肯定优先玩Nim游戏；如果后手试图破坏局面，将某个偶位置上的若干石子移动到了左边的奇位置i上，那么先手可以将这若干个刚移到i的石子继续移动到i左边的偶位置上，对Nim局面依然没有任何影响，除非后手回头来继续动奇位置的石子，那也只能是输。
　　那么如果Nim游戏先手必败，也是同理，后手可以用相同的方式迫使先手玩Nim游戏，直到输为止。
　　因此，奇数位置的石子的相关信息，就直接决定了阶梯Nim问题的结果。

sg函数相关知识

sg定理：对于任意一个状态x，如果sg(x)=0说明x为必败态，!=0为必胜态
定义其sg函数值sg(x)为不属于其所有后续状态的sg函数值集合的最小非负整数
至于证明过程可以自己画图感受感受
sg(x)=mex(S),其中S是x的后续状态的sg函数值集合
比如x有5个后续状态，其中sg函数值分别是1,5,2,0,4，那么sg(x)=3
也就是我们可以通过求出x的所以后续状态的情况，来反推x的情况
对于某个游戏和（n个序列进行），其sg函数为其子游戏（每个序列）的sg函数的nim异或和。这n个序列都是独立的彼此互不相关
这样多组问题我们就可以分别求出每组情况，然后异或的最后答案