题解：P10254 口吃

· · 题解

首先，一个排列 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) 的时间复杂度解决此题。