题解：AT_arc135_f [ARC135F] Delete 1, 4, 7, ...

· · 题解

下标 k 经过还原成了 f(k) = \left\lfloor\dfrac{3k+1}{2}\right\rfloor。假设 f^i(k) 表示将 f 迭代 i 次带入 k。假设最终长度

N' = \left\lfloor \dfrac{2^K \cdot N}{3^N} \right\rfloor.

欲求

\mathrm{Ans}(N, K) = \sum_{0 < i \le N'} f^K(i).

对 x 连续 K 次操作后，主项为 \dfrac{3^K x}{2^K}，误差项仅与 x \bmod 2^K 有关，因此假设 C : [0, 2^K) \to \mathbb Z，使得

f^K(x) = \dfrac{3^K x + C(x \bmod 2^K)}{2^K}.

因此按 2^K 分组后形成 d = 3^K 的等差数列。

比如说，我们取 K = x+y，将 f^K 分解为 f^x \circ f^y。那么我们可以写

\mathrm{Ans}(N,K)= \dfrac{3^x}{2^x}\left(\sum_{0 < i \le N'} f(i,y) − \sum_{0 \le i < 2^x} i \cdot \mathrm{cnt}(i) \right) + \sum_{0 \le i < 2^x} f^x(i) \cdot \mathrm{cnt}(i).

其中

\mathrm{cnt}(i)

是 f^y(k) \bmod 2^x = i 的个数。那么我们只考虑三件事，分别对应三项。

对于

A = \sum_{0 < i \le N'} f(i,y)

一项，我们可以考虑写成 i \bmod 2^y 一项和一个误差项。这当然可以 2^y 扫一遍。

而考虑 t_s = t_0 + s 3^y 这一式给出了 t_s \bmod 2^x 是一个等差数列，故可以直接用差分遍历 2^x 个循环计算 \rm cnt。那么我们当然可以通过查表计算 \rm Ans。时间复杂度是 \tilde {\operatorname{\mathrm O}}\left(2^{K/2} \log N\right)（本文中 \sim 记号还表示忽略一个 {\rm poly}(K) 的倍数）。

看起来不太能通过，但是我们还可以缝合上一个暴力，时间复杂度 \tilde {\operatorname{\mathrm O}} (N \cdot {(2/3)^K})。

那么平衡一下：2^{K/2} \log N = N \left(\dfrac 23\right)^K，即大致有 \dfrac{\log N}{K} 约为

c = \dfrac 12 \log 2 - \log \dfrac 23 = \dfrac 12 \log \dfrac 92.

带入得时间复杂度

\tilde {\operatorname{\mathrm O}} (N^\alpha), \alpha = \dfrac {\log 2}{\log (9/2)} \approx 0.461.

精细控制可以将复杂度内的 K 或 {\rm polylog}(N) 相关控制在 \mathrm{polylog}(K) 或 \mathrm{poly}(\log \log N) 量级。