algorithm - Topcoder SRM 624 DIV II 3 级

Question

谁能解释一下这个问题的解决方法，你可以在这里查看问题: http://community.topcoder.com/stat?c=problem_statement&pm=13204和这里的解决方案: http://apps.topcoder.com/wiki/display/tc/SRM+624

我其实不明白数的计算和最小排除序数的选择是如何导致解决方案的。

Answer 1

我为这个问题苦苦挣扎，在 SRM 结束后我试图自己解决它，但找不到解决方案，所以我决定阅读社论。

问题中呈现的游戏是一个公平的游戏，使用正常的游戏规则，因此基于 Sprague-Grundy 定理，它等同于 Nim 游戏，其中每个状态都可以用一个数字来表示。

Nim 游戏已经解决，甚至由多个单独的 Nim 堆组成的组合 Nim 游戏也已解决，因此有一种方法可以找出在此类游戏中哪些玩家具有获胜策略。这是使用代表游戏状态的数字来确定的。如果从当前位置无法移动，则该位置的编号为 0。否则，根据 Sprague-Grundy 定理，该位置的编号是未出现在以下编号集合中的最小非负整数可以从当前位置一步到达。

这篇论文对我理解数字理论有很大帮助:http://web.mit.edu/sp.268/www/nim.pdf .至于Sprague-Grundy定理的证明，我找到了one from Wikipedia更容易理解。