game-theory - 斯普拉格格兰迪定理

Question

我一直在尝试解决http://www.spoj.com/problems/MATGAME/这个关于 spoj 的问题。这个问题可以使用 sprague grundy 定理来解决。计算每行的 sprague Grundy Number，如果这些值的 XOR(^) 为 0，则第二个玩家首先获胜。我不明白如何获得每一行的脏数字。

Answer 1

一般感知
如果第一个数字大于第二个数字，则该行的 Grundy 值是第一个数字，否则 Grundy 是第一个数字 - 1。

伪代码如下所示：

ans := 0
for i from 1 to N
    temp := 0
    for j from M down to 1
        if temp is greater or equal to val[i,j]
            temp := val[i,j] - 1
        else
            temp := val[i,j]
        end if
    end for
    ans := ans ^ temp
end for
if ans is equal to 0
    print SECOND
else
    print FIRST