题解

思路

Alice 选定初始位置后，轮到 Bob 从该位置行动。因此一个位置是幸运的，当且仅当“轮到当前玩家、筹码位于该位置”的状态是必败态。

本题采用反常规则：没有合法移动的玩家获胜。所以没有更小前驱的位置是必胜态，而不是通常博弈中的必败态。

做法

按位置从左到右处理。当前位置的所有后继都已经被判定：

• 若不存在值更小的前驱，则当前位置无路可走，是必胜态；
• 若存在一个值更小的必败前驱，当前玩家可把必败态留给对手，所以当前位置是必胜态；
• 否则存在合法移动但所有后继均为必胜态，当前位置才是必败态，也就是幸运元素。

要判断第一种情况，只需维护此前出现值的最小值。要判断第二种情况，只需维护此前所有必败位置中值的最小值。设当前位置的值为 $x$，当且仅当“此前最小值小于 $x$”且“最小必败值不小于 $x$”时，当前位置为必败态。

处理完当前位置后更新这两个最小值。每个位置只做常数次操作。

正确性证明

按位置归纳。处理当前位置时，所有可达位置都在它左侧，其胜负态已由归纳假设正确求出。

若不存在更小前驱，当前位置没有合法移动，按规则当前玩家获胜。若存在更小的必败前驱，当前玩家选择它即可获胜。其余情况下至少有一步可走，且每一步都到达必胜态，所以无论怎样移动都会把必胜局面交给对手，当前位置必败。算法的两个最小值分别准确判断上述两个存在性条件，因此对当前位置的判定正确。由归纳法，所有位置均被正确判定，统计出的必败位置数就是幸运元素数。

复杂度分析

每组测试的时间复杂度为 $O(n)$，额外空间复杂度为 $O(1)$。

子任务说明

• $n\le12$ 时可直接递归展开完整博弈树。
• $n\le3000$ 时可按位置递推，并扫描所有更早位置，复杂度为 $O(n^2)$。
• 满数据使用两个最小值完成 $O(n)$ 判定。