题解：CF2169D2 Removal of a Sequence (Hard Version)

2huk · 2025-12-05 09:11:30 · 题解

进行一次操作后，若原来第 k 个数变到了第 k' 个位置，应满足 k'= k - \lfloor k/y \rfloor，即每 y 个分一组，并取走每组的最后一个数。

反过来考虑，我们将操作后的序列每 y-1 个分成一组，那么每组的后面原本有一个数但是现在删除了。那么如果要从 k' 推到 k，相当于计算 k' 之前有多少个被删除的，即有多少个完整的大小为 y-1 的组。显然是 \lfloor (k'-1) / (y-1) \rfloor。所以 k=k'+\lfloor (k'-1) / (y-1) \rfloor。

所以 Easy Version 的做法就是：

y -- ;
while (x -- ) k += (k - 1) / y;

为了下面好描述我们将 y --。

考虑优化。根据数论分块，分母固定时，使整个式子下取整后不同的分子只有根号种。于是可以求出，对于当前 k，最大的 r 使得 \lfloor (r-1)/y \rfloor = \lfloor (k-1)/y \rfloor。那么当 k 不超过 r 时，每次增加的都是固定的 \lfloor (k-1)/y \rfloor。模拟这个过程即可。

y -- ;
while (x && k <= 1e12) {
    int t = (k - 1) / y;
    if (!t) break;
    int r = y * t + y;
    int cnt = min(x, (r - k) / t + 1);
    x -= cnt;
    k += t * cnt;
}