阶梯博弈

阶梯博弈：博弈在一列阶梯上进行,每个阶梯上放着若干个点,两个人进行阶梯博弈，每一步则是将一格上的若干个点(>0)移到前面一格,最后没有点可以移动的人输。（地面上无法移动）

结论：奇数编号的阶梯异或和为0先手必败，否则必胜。

我们将阶梯从下到上标号为1~n，将每一个台阶看作独立的游戏。

首先证明偶数编号的台阶是必败态（SG函数值为0）。

如果先手移动满足条件的若干点，那么后手一定可以将这些移动后在B中相等数量的点向前移动一次，对于所有偶数编号的阶梯来说，最后一定是后手完成最后一次操作，所以先手必败。

对于奇数编号的台阶来说，它一定会将点移动到一个偶数编号的台阶里，那么它对其他台阶的影响是可以不用考虑的（偶数为必败态）。所以可以将所有的奇数台阶看作一个独立的Nim游戏。

最后总的SG函数值就是每一个奇数台阶的异或和。