自动搬运

查看原文

来自洛谷，原作者为

	zhouyuhang Bénédiction de Dieu dans la solitude

搬运于2025-08-24 23:03:52，当前版本为作者最后更新于2024-08-03 16:51:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一些与正解无关的暴力略去不提（如暴力 dp，找规律等），这些大致有 40 分。

Hint 1

考虑所有后手必胜点，不难发现，如果 $x, y$ 同为后手必胜点，则必有 $x \not\equiv y \pmod n$。否则不妨设 $x < y$，$y$ 个石子时只需取 $y - x$ 个石子即可从一个后手必胜点到达另一个后手必胜点，这无疑导出了矛盾。

换言之，在所有 $x \bmod n = r$，只会有一个 $x$ 是后手必胜点。因此，我们在 dp 时无需枚举每一个 $n$ 的倍数去转移，只需记录对每个 $r \in [0, n)$ 记录此前是否有 $x \equiv r \pmod n$ 的后手必胜点 $x$。这样即有 $O(m \sqrt n)$ 的复杂度，结合暴力有 55 分。

Hint 2

以下证明：后手必胜点的最大值不超过 $n (\sqrt n + 1)$。

考虑一个后手必胜点 $x$ 满足 $\forall p < x \land p \equiv x \pmod n$ 均为先手必胜点，则对每一个这样的 $p$，记 $\{ p - k ^ 2 \mid k \in \mathbb Z^+, k ^ 2 \le \min(n, p)\}$ 中的后手必胜点数为 $r(p)$，则有 $r(p) \ge 1$。而根据 Hint 1，对于每个 $k ^ 2 \le n$，$\{p - k ^ 2 \mid p \equiv x \pmod n, k ^ 2 \le p < x\}$ 至多有一个后手必胜点，从而有 $\sum _ {p < x, p \equiv x \pmod n} r(p) \le \sqrt n$，因而这样的 $p$ 的数量不超过 $\sqrt n$，从而有 $x < n (\sqrt n + 1)$。

应用这一结论，上文中 $O(m \sqrt n)$ 的 dp 复杂度降至 $O(n ^ 2)$。实际测试可以发现，这个上界很松，实际在 $n \le 10 ^ 5$ 时，最大值不超过 $10 ^ 7$，进行一定卡常后一共可以得到 85 分。

正解

注意到，后手必胜点最多只有 $n$ 个。因此，我们只需将转移改为从后手必胜点开始的主动转移即可做到 $O(n \sqrt n)$。