专栏文章

题解：P14111 [ZJCPC 2017] Chiaki Sequence

NNaCly_Fish绒布球
P14111题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@minoe2o4
此快照首次捕获于
2025/12/02 05:43
3 个月前
此快照最后确认于
2025/12/02 05:43
3 个月前
查看原文
有点神秘的 adhoc 题。
首先这题中出现的数列在 OEIS 中是有记录的，但是没提供什么有助于解题的信息，只能我们自己分析了...
观察 {an}\{a_n\} 的递推式，发现问题的关键在于分析 r2n+1r_{2n+1}，可以打出如下一个表：
CPP
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
大部分相邻项之差都是 11，这是因为 a2n=a2n−1+r2n−1a_{2n}=a_{2n-1}+r_{2n-1}，此时 r2n−1∈S2nr_{2n-1}\in S_{2n}，让最小未出现的数增加了 11。但是「乘 22」这个操作会给 SS 中加入许多较大的数，这会对数列 rr 的计算在之后产生影响。
为了规避这种影响，我们考虑这样一件事：rnr_n 有一个很宽松的上界是 n2n^2，因为 nn 个数两两之差就最多有 n(n−1)/2n(n-1)/2 种。而输入的 nn 都不超过 N=10100N=10^{100}，我们可以预处理出 {an}\{ a_n \} 的前 BB 项，使得 aB>N2a_B > N^2，然后我们维护集合 Tn=Sn∩[1,N2]T_n=S_n \cap [1,N^2]。
如此可以发现，对于 n>Bn>B：
Tn={Tn−1 , 2∤nTn−1∪{mex⁡(Tn−1)} , 2∣nT_n=\begin{cases} T_{n-1} \ , \ 2 \nmid n \\ T_{n-1}\cup \{\operatorname{mex}(T_{n-1})\} \ , \ 2 \mid n\end{cases}
而从 rBr_B 到 rNr_N 的变化可以划分为 Θ(B2)\Theta(B^2) 个连续段，在每个连续段上都有 ri=ri−2+1r_i=r_{i-2}+1。根据 TBT_B 可以将这些连续段处理出来，之后每个连续段上的 aia_i 之和就能直接 Θ(log⁡N)\Theta(\log N) 计算了。别忘了对每个连续段的结果做前缀和，这样每次询问只需求一个不完整的连续段即可。
最后来分析一下 BB 的取值，由于 an≥2n/2a_n \geq 2^{n/2}，所以有 B=O(log⁡N)B =\mathcal O(\log N)，总时间复杂度就是 O(log⁡3N+Tlog⁡Nlog⁡log⁡N)\mathcal O(\log^3 N + T \log N \log \log N)。

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...