题解：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$。假设最终长度

欲求

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

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

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

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

对于

一项，我们可以考虑写成 $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}$ 约为

带入得时间复杂度

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