题解：P14111 [ZJCPC 2017] Chiaki Sequence

· · 题解

有点神秘的 adhoc 题。

首先这题中出现的数列在 OEIS 中是有记录的，但是没提供什么有助于解题的信息，只能我们自己分析了...

观察 \{a_n\} 的递推式，发现问题的关键在于分析 r_{2n+1}，可以打出如下一个表：

4, 5, 9, 10, 11, 16, 18, 22, 23, 24, 25, 27, 28, 29, 31, 32, 33, 36, 37, 39, 42, 44, 45, 46, 48, 52, 53, 54, 55, 56, 57, 58, 59, 62, 63, 64, 65, 66, 67, 68, 69, 71, 72, 73, 74, 75, 76, 77, 78

大部分相邻项之差都是 1，这是因为 a_{2n}=a_{2n-1}+r_{2n-1}，此时 r_{2n-1}\in S_{2n}，让最小未出现的数增加了 1。但是「乘 2」这个操作会给 S 中加入许多较大的数，这会对数列 r 的计算在之后产生影响。

为了规避这种影响，我们考虑这样一件事：r_n 有一个很宽松的上界是 n^2，因为 n 个数两两之差就最多有 n(n-1)/2 种。而输入的 n 都不超过 N=10^{100}，我们可以预处理出 \{ a_n \} 的前 B 项，使得 a_B > N^2，然后我们维护集合 T_n=S_n \cap [1,N^2]。

如此可以发现，对于 n>B：

T_n=\begin{cases} T_{n-1} \ , \ 2 \nmid n \\ T_{n-1}\cup \{\operatorname{mex}(T_{n-1})\} \ , \ 2 \mid n\end{cases}

而从 r_B 到 r_N 的变化可以划分为 \Theta(B^2) 个连续段，在每个连续段上都有 r_i=r_{i-2}+1。根据 T_B 可以将这些连续段处理出来，之后每个连续段上的 a_i 之和就能直接 \Theta(\log N) 计算了。别忘了对每个连续段的结果做前缀和，这样每次询问只需求一个不完整的连续段即可。

最后来分析一下 B 的取值，由于 a_n \geq 2^{n/2}，所以有 B =\mathcal O(\log N)，总时间复杂度就是 \mathcal O(\log^3 N + T \log N \log \log N)。