题解：P17226 [Math×Girl²] 终末电台

nbhs23a28 · 2026-08-10 10:18:37 · 题解

我不会数论怎么办？

阅读本文所需要知道的唯一数论前置知识：二次剩余判定。

我们充分发扬打表直观，显然在 p,k 较小时有个三次方级别的 DP，我们尝试把 k 小时每一项列出来，注意到即使 p,k 远大于 3，k 一定的 f 序列中都恰有 3 种不同的值，并注意到恰对应模 p 意义下 0，二次剩余，非二次剩余。

这启发我们将之看成三个等价类，每次转移系数显然是固定的，故显然可以矩阵快速幂优化 DP 做到单次询问 O(w^3\log k)（w 代表矩阵大小，此处等于 3），通过预处理矩阵关于 2 的幂次查询时向量乘矩阵能做到 O(w^3\log k)-O(w^2\log k)。

考察转移系数，发现根据 p 模 4 可以进行分讨。首先，由于不会数论，以下二次剩余与非二次剩余间转移结论来源于打表，（包括上文的为何是等价类）严格证明可以参照官方题解。记二次剩余等价类为 1，非二次剩余等价类为 2，则：

• 当 p 模 4 余 1 时：从 0 到 1 转移数为 \frac{p-1}2，从 1 到 0 转移数为 1，从 1 到 1 转移数为 \frac{p-1}4-1，从 1 到 2 转移数为 \frac{p-1}4，从 2 到 1 转移数为 \frac{p-1}4，从 2 到 2 转移数为 \frac{p-1}4，其余转移数为 0；
• 当 p 模 4 余 3 时：从 0 到 1 转移数为 \frac{p-1}2，从 1 到 1 转移数为 \frac{p-3}4，从 1 到 2 转移数为 \frac{p-3}4+1，从 2 到 0 转移数为 1，从 2 到 1 转移数为 \frac{p-3}4，从 2 到 2 转移数为 \frac{p-3}4，其余转移数为 0。

根据转移系数列出矩阵即可，具体无需多言。

最后我们只需判断 n 在哪个等价类即可，通过常识二次剩余判定：n^{\frac{p-1}2} 是否模 p 余 1 即可。