考虑每一层的 SG 函数,最终结果由每一层的 SG 函数的异或和决定。
如果 m 为偶数,设左右各有 l,r 个积木,显然 SG(l,r)=(l+r)mod2。
如果 m 为奇数,设最中间的位置左右各有 l,r 个积木,SG 函数记作 SG(l,0/1,r):
- 如果最中间没有积木:等价于 m 为偶数的情况
- 否则,如果 l=0 或 r=0,只能从一边取,SG(0,1,x)=xmod2
- 否则,如果 l=1 或 r=1,不妨记作 (1,1,x),我们可以到达 (0,1,x),(1,0,x),(1,1,x−1) 三种状态。注意到 (0,1,x) 和 (1,0,x) 的 SG 函数必然一个为 0 一个为 1。但 (1,1,x−1) 的 SG 函数不容易看出规律,我们观察一下 x 比较小的情况:SG(1,1,1)=2,SG(1,1,2)=3,SG(1,1,3)=2,可以发现 SG(1,1,x)=2+(x+1)mod2
- 否则,观察到 SG(2,1,2)=1,通过数学归纳法可以推出 SG(l,1,r)=(l+r+1)mod2