自动搬运

查看原文

来自洛谷，原作者为

	sunkuangzheng **

搬运于2025-08-24 23:09:56，当前版本为作者最后更新于2025-02-14 18:21:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目所求式子即为 $\sum \limits_{i=1}^n p_i(n-i+1)$。

注意到字典序前 $S$ 小的排列里，只有最后 $20$ 个位置可能满足 $p_i \ne i$，因为 $20!$ 已经大于 $10^{18}$。

首先求出字典序第 $S$ 小的排列 $q$，然后枚举 $p$ 和 $q$ 的 LCP 长度 $l (l \ge n-20)$，那么此时应当有 $p_{1\sim l} = q_{1 \sim l}$。贪心的，此时 $p_{l+1}$ 应当填写小于 $q_{l+1}$ 的最大数字，后面的数字降序排列。

时间复杂度可以做到 $\mathcal O(T \log^2 n)$，可以进一步使用数据结构优化至 $\mathcal O(T \log n \log \log n)$，但是在该数据范围下是没有必要的。