模拟赛 4 题解 | AlanSP's Blog

思维+状压dp+博弈论+数学+模拟

我们要是判断符号的话，只需要存在 $1，1$ 和 $10$ 。

稍微思考一下，答案只可能是 $0$ 或 $1$ 或 $2$ ，答案的不同取值只取决于每一位。

我们把每一位分开考虑，那么答案就是需求最多的位/

首先我们可以考虑 $sg$ 函数的求法，即一个棋盘能够转移到哪些状态。

设当前棋盘长度为 $n$ ，如果在边界放一个棋子，会转移到 $n-2$ 。

而如果在中间的位置放棋子，那么会分裂成两个小棋盘 $j$ 和 $n-j-3$ ，当前状态的 $sg$ 即为这两个小棋盘的 $xor$ 。

根据 $sg$ 定理，长度为 $n$ 的棋盘的 $sg$ 是所有后继状态的 $mex$ 。

这样我们可以求出任意长度棋盘的 $sg$ 函数了。

打表发现，除第一个周期略有变化， $sg$ 只总是以 $68$ 为周期。

那么就可以特判+打表+ $sg$ 定理异或过掉此题。

直接模拟就好，注意对齐和侧面旋转。