P8181 Circle 题解

unputdownable · 2022-02-26 22:38:03 · 题解

考虑如何求出 J_m(n)。

递归，如果 n < m，J_m(n)=1；

如果 n \geq m，考虑报一遍 1-m：

所以有：

于是可以将 n 按模 m-1 分类，这样在每一类中，除了若干个 J_m(n)=n 的位置外，都是公差为 m 的等差数列。

考虑每一类中有哪些不满足等差的位置（下称断点）。

由于 J_m(n)=n 的下一项必然是 1，所以一个 1 对应一个断点。

思考 J_m(n) 什么情况下为 1：

上面提过 1 \leq n < m 的时候是 1；

当 n \geq m 时，易得 n 必然是 m 的倍数，否则报完一圈后 1 一定当场出局，于是除 m 后归纳。

可得断点只有 k \times m^a 的形式，其中 1 \leq k \leq m-1。

那么每个同余类中就只有 \log 个断点（k \times m^a 正好在 k 这个同余类中），拆成 \log 个等差数列分别求和即可。

这样就得到了一个 \Theta(m\log_m a) 的算法。

对于每一个 i 暴力找出其前面最后一个断点，就能得到一个 \Theta(\log_m a) 的单点求值算法。

两者结合起来可以得到 55 分的好成绩。

继续观察第 k 组的答案。

事实上断点是 k \times m^a 的形式，而点的个数是 \lfloor \frac{n-k}{m-1}+1 \rfloor。

只要断点的个数相同，并且点的个数相同，那么可以发现答案就是关于 k 的不超过 2 次的多项式。而断点个数和点的个数都只有两种，所以按这个把要算的东西分成三段，对每一段插值算即可。

时间复杂度 \Theta(\log_m a)。