题解 | #SG函数#

题解

1. 状态简化

设两列当前的最高占据层数分别为 ，记 ，剩余高度 ，差值 。注意每次操作只会让 变化 或 ，因此 始终为偶数。

初始状态满足 。我们只需分析所有 的状态（称为“平衡态”），并证明从平衡态出发的最优策略只依赖 。

平衡态 的三种合法落子：

• 横向 2×1：两列同时加 1，高度上界变为 ，故 （需 ），仍保持平衡态。
• 2×2 方块：两列同时加 2，（需 ），仍保持平衡态。
• 纵向 2×1：放在任一列使该列高度加 2，得到不平衡态 （需 ）。

关键观察：对任意不平衡态 ，当前玩家总能在较低列再放一个纵向 2×1，使其回到平衡态 ，且 不变（该操作合法，因为较低列高度为 ，放置后刚好达到 ）。

因此，从平衡态出发，选择“纵向 2×1”得到 ，对手可以立即回到 。这说明该走法对当前玩家而言不优于直接选择“2×2 方块”走到 。故在平衡态的最优策略分析中，可以忽略走向不平衡态的选择。

于是，平衡态的可行转移仅为 或 ，与“一堆 个石子，每次取 1 或 2 个”的游戏等价。

2. SG 函数

设 为剩余高度 时的 Grundy 值，递推：

计算前几项：

	后继
0	—	0
1		1
2		2
3		0
4		1
5		2
6		0

易得 ，周期为 3。

3. 胜负判定

初始状态 ，故 。

• 若 ，，先手必败 → Bob
• 否则 ，先手必胜 → Alice

4. 复杂度

单组 判断 ，总复杂度 。注意到 ，直接取模即可（开long long）。