题解 P8145【[JRKSJ R4] kth】

· · 题解

\text{Link}

## 题意 给你一个 $n$ 阶排列 $p$，任选一个起始点，走 $m-1$ 步，并将走过的所有数按走到的顺序写下，形成一个长度为 $m$ 的序列。求出所有以上面的方法生成的序列中字典序第 $k$ 小的序列的所有元素的和。 $n\le2\times 10^7$，$m,k\le10^{18}$。 ## 思路 先特判掉 $n\le 2$ 的情况，接下来默认 $n\ge 3$。 设 $f_{i,j}$ 表示从 $i$ 出发走 $j$ 步的方案数，转移显然。按 $p_i$ 从小到大枚举起始点，如果 $f_{i,m-1}<k$ 则将 $k$ 减去 $f_{i,m-1}$，否则我们就确认了起始点为 $i$ 即序列第一位为 $p_i$。接下来的每一步也是类似的，对第 $i$ 步，不妨设现在在 $x$ 且 $p_{x-1}<p_{x+1}$，则判断 $f_{x-1,m-i}$ 与 $k$ 的大小关系即可。 时间复杂度 $O(nm)$，无法通过。 $f_{i,j}$ 的值可能很大，而 $k\le 10^{18}$ 且我们只需要比较 $f_{i,j}$ 与 $k$ 的大小关系。于是当 $f_{i,j}\ge k$ 时，不妨令 $f_{i,j}=+\infty$。注意到 $j\ge 2\log k$ 时 $f_{i,j}$ 必然为 $+\infty$（这个下界只在 $n=3$ 时取到）。令 $c=2\log k$，可以发现除了最后 $c$ 步需要决策，其余全部向相邻位置中较小的走。 考虑前面的部分，一定是走到某个地方开始在 $i$ 和 ${i+1}$ 之间反复走。所以我们可以 $O(n)$ 走完前面的步数，最后 $c$ 步按照决策来走。 时间复杂度 $O(n\log k)$，无法通过，瓶颈仍在计算所有 $f_{i,j}$。 继续优化 $f_{i,j}$ 的预处理。由于我们只需要求走不超过 $c$ 步的方案数，所以如果 $c<i<n-c$，则 $i$ 走 $c$ 步的过程中不可能碰到边界，即 $f_{i,j}=2^j$。于是我们只需要求 $i\le c$ 和 $i\ge n-c$ 的这 $O(\log k)$ 个位置的 $f_{i,j}$ 即可。 时间复杂度 $O(n+\log^2k)$，可以通过。