我在 这个帖子 中“证明”了不需要“先手不能左移,后手不能右移”的限制,至少说证明本身是伪的,我谢罪,感谢 @精神小火 指出问题。(当然保持对第一篇题解的控诉,所以不撤回了 qwq。)
但经查阅 SDOI 2011 省选原题,我发现原题并没有这个限制。如果省选标算做法仍然一致,即仍然能够推导出 K-Nim 博弈胜负等价于原局面胜负,我手玩不出来这个局面:
初始:.ABA...BA...BA...B(. 是一个空格),m=2m=2m=2。依照结论,先手 A 必败;
.ABA...BA...BA...B
.
A
A 移动:A.BA...BA...B.A..B,对称字符串(在没有那个限制的前提下)与原局面等价,B..A.B...AB...AB.A,把 B 视为 A',A 视为 B',可见 A' 先手必败,即原局面 B 先手必败。
A.BA...BA...B.A..B
B..A.B...AB...AB.A
B
A'
B'
所以,为什么 A 的必败态直接转移到 B 的必败态?省选原题有没有锅?到底该怎么做?/yiw