自动搬运

查看原文

来自洛谷，原作者为

	NaCly_Fish 北海虽赊，扶摇可接。

搬运于2025-08-24 22:56:14，当前版本为作者最后更新于2024-03-18 01:11:12，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

首先，一个排列 $a$ 的权值是：

$$\frac{n(n+1)(2n+1)}{6}+\sum_{i=1}^n\sum_{j=1}^{i-1}[a_i < a_j](a_i-a_j) $$

这个在官方题解中就有证明，大致方法是从权值最大的排列（顺序排列）开始，考察交换两个顺序项时产生的权值变化即可证明。

现在考虑对后面一部分计数，首先设生成函数 $F_1(x,y)$，用 $x$ 这一维计量逆序对数，$y$ 这一维计量上式中的 $a_j$ 之和，则：

$$F_1(x,y)=\prod_{i=1}^n \left( \sum_{j=0}^{i-1}x^j y^{ij}\right)=\prod_{i=1}^n \frac{1-(x y^i)^i}{1-xy^i} $$

解释一下这个式子：从小到大插入 $i$，这时 $i$ 是当前序列中的最大值。若插入的位置会产生 $j$ 个逆序对，则会对总和贡献 $ij$。

类似地设 $F_2(x,y)$，不过 $y$ 计量的是 $a_i$：

$$F_2(x,y)=\prod_{i=1}^n \left( \sum_{j=0}^{n-i}x^j y^{ij}\right)=\prod_{i=1}^n \frac{1-(x y^i)^{n-i+1}}{1-xy^i} $$

这时是从大到小插入 $i$，含义是一样的。所以最终答案就是

$$\frac{n(n+1)(2n+1)}{6}f_{n,k}+[x^k]\left( \frac{\partial (F_2(x,y)-F_1(x,y))}{\partial y} \right)\bigg|_{y=1} $$

其中 $f_{n,k}$ 表示有 $k$ 个逆序对的 $n$ 阶排列数。前面一项容易计算，只用考虑后面这一部分。求导后展开就得到：

$$[x^k]\left(\prod_{i=0}^n \frac{1-x^i}{1-x} \right)\sum_{i=1}^n \frac{x + x^i (i (x - 1) - x)}{1-x^i}(n-2i+1) $$

前面这部分连乘可以 $\Theta(k \log k)$ 求系数，后面这个和式暴力即可。因为 $k$ 次以内的 $1/(1-x^i)$ 只有 $\lfloor k /i \rfloor$ 项系数非零，直接计算的时间复杂度就是 $\Theta(k \log n)$。

这样就可以做到 $\Theta(k \log k)$ 的时间复杂度解决此题。