「TPOI-1B」ASPAP Solution

sunkuangzheng · 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)，但是在该数据范围下是没有必要的。