Topcoder SRM 624 DIV II三级

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，其中每个状态都可以由nimber表示。

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

这篇论文帮助我理解了nimber理论：http://web.mit.edu/sp.268/www/nim.pdf。至于斯普拉格-格朗迪定理的证明，我发现one from Wikipedia更容易理解。