Nim问题和阶梯Nim（staircase nim）

Nim问题：

有若干堆石子，每堆石子的数量都是有限的，合法的移动是“选择一堆石子并拿走若干颗（不能不拿）”，如果轮到某个人时所有的石子堆都已经被拿空了，则判负（因为他此刻没有任何合法的移动）。

也可以说有 N 堆石子，第 i 堆有 A[i] 个石子，两个人轮流取，每次至少取 1 个石子，最多把该堆石子都取完（假设两个人都足够聪明）。

现在需要求的是谁先手的那一方能不能赢得比赛。

这个问题如果自己慢慢想的话是很难想出一个结果来的，这里直接给出结论，具体的证明过程不用深究。

res = A[0] ^ A[1] ^ A[2] ^…… A[n]

把每一堆石子的数量进行异或操作，得到结果 res。

若 res != 0，则先手必胜；

若 res == 0，则先手必败；

考虑必胜的局面，就是当先手面对只有一堆石子的情况，这个时候直接全部取走就可以获胜，

而这种情况 res 一定满足 res != 0。

并且在异或操作中只需要一步就可以把 res != 0 的情况转化成 res == 0 的情况。

因此如果先手面对的局面 res != 0 的话，他就可以一步取走某个数量的石子，

将 res == 0 的局面对给对方。

而在 res == 0 的局面下，不管如何取石子，都会破坏这个局面成为 res != 0 的情况。

先手方下回合继续执行上面的步骤即可，这样最终就可以获得游戏胜利。

阶梯Nim问题：

怎么使用 Nim 来解决问题呢？

对奇数阶的石头进行 Nim，偶数阶的石头对结果不影响。

如上图：res = 2 ^ 3 ^4 = 5 不为 0，故先手必胜

把石头从奇数阶上移到偶数阶上相同于 Nim 中取一次石子。

为什么是奇数阶？

因为最后石子都要到 0 上，从 1 到 0 就是最后一步，这是从奇数阶到偶数阶，

所以认为从奇数阶上移到偶数阶上相当于取一次石子才能保证状态一致。

若 res != 0，先手将非 0 的局面转为 0 的局面，即把部分石子从奇数阶挪到下层偶数阶。

此时对手只有两种选择：

① 挪动奇数阶上的石头，从而打破了 0 的局面，再一次把非 0

的局面留给先手方，先手方继续调整奇数阶的石子即可。

② 挪动偶数阶上的时候到下层的奇数阶上，先手只要将这些刚挪下来的石子继续下挪，

这样奇数阶上的石子数量保持不变，又把 0 的局面留给对手。

这样一来，就能保证先手必胜了。

【END】感谢观看