自动搬运

查看原文

来自洛谷，原作者为

	Sol1 博客：sol1.netlify.app

搬运于2025-08-24 22:33:02，当前版本为作者最后更新于2021-04-21 22:55:13，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

upd. 把那个大公式改得稍微好看一点…要不然太长了

---

idea 为原题改编

设 $I$ 为全局逆序对数量，以及：

$$\begin{cases}f(n)=\sum_{i=0}^n[n]_i\\g(n)=\sum_{i=0}^n(i+1)[n]_i\\h(n)=\sum_{i=0}^n(i+1)^2[n]_i\end{cases} $$

其中 $f,g,h$ 均有线性递推式：

$$\begin{cases}f(n)=1+nf(n-1)\\g(n)=1+n[g(n-1)+f(n-1)]\\h(n)=1+n[h(n-1)+2g(n-1)+f(n-1)]\end{cases} $$

对于 $i<j\leq n$，考虑在哪些方案中 $a_i$ 和 $a_j$ 会被交换。

情况 $1$：子序列中同时出现 $i,j$，且重新排列之后 $j$ 换到 $i$ 前面。

考虑枚举子序列长度，得到方案数为：

$$\begin{aligned}&\sum_{k=0}^{n-2}\binom{n-2}{k}\cdot \dfrac{(k+2)!}{2}\\=&\sum_{k=0}^{n-2}\dfrac{(n-2)!}{k!(n-2-k)!}\cdot\dfrac{k!\cdot(k+1)\cdot(k+2)}{2}\\=&\sum_{k=0}^{n-2}\dfrac{(k+1)\cdot(k+2)}{2}[n-2]_k\\=&\dfrac{g(n-2)+h(n-2)}{2}\end{aligned} $$

情况 $2$：$i$ 在子序列里面，$j$ 不在子序列里面，重新排列后 $i$ 被放到了 $j$ 后面。

考虑枚举有几个子序列的元素出现在 $j$ 前面，以及有几个出现在 $j$ 后面。

得到下式：

$$\sum_{k=1}^{n-j}\sum_{l=0}^{j-2}\binom{n-j}{k}\binom{j-2}{l}k(k+l)! $$

拆定义式变形：

$$\sum_{k=1}^{n-j}\sum_{l=0}^{j-2}\dfrac{(n-j)!}{k!(n-j-k)!}\cdot\dfrac{(j-2)!}{l!(j-l-2)!}\cdot k(k+l)! $$

提出 $n-j$，约去 $k$：

$$(n-j)\sum_{k=1}^{n-j}\sum_{l=0}^{j-2}\dfrac{(n-j-1)!}{(k-1)!(n-j-k)!}\cdot\dfrac{(j-2)!}{l!(j-l-2)!}\cdot (k+l)! $$

组合数定义式变形：

$$(n-j)\sum_{k=0}^{n-j-1}\sum_{l=0}^{j-2}\binom{n-j-1}{k}\binom{j-2}{l}(k+l+1)! $$

调换枚举顺序（先枚举 $k+l$）：

$$(n-j)\sum_{k=0}^{n-3}(k+1)!\sum_{l=0}^{j-2}\dbinom{n-j-1}{k-l}\dbinom{j-2}{l} $$

沃德你蒙德恒等式变形：

$$(n-j)\sum_{k=0}^{n-3}(k+1)!\dbinom{n-3}{k}$$

拆定义式变形：

$$(n-j)\sum_{k=0}^{n-3}(k+1)[n-3]_k$$

代入预设函数：

$$(n-j)g(n-3)$$

情况 $3$：$j$ 在子序列里面，$i$ 不在子序列里面，重新排列后 $j$ 被放到了 $i$ 前面。

类似情况 $2$ 可以得到情况数为 $(i-1)g(n-3)$

全部合起来再加上全局逆序对的贡献就得到区间 $[1,n]$ 的答案式：

$$\text{Ans}(1,n)=f(n)\cdot I-\sum_{i=1}^n\sum_{j=i+1}^n \operatorname{sgn}(a_i-a_j)\cdot\left[\dfrac{h(n-2)+g(n-2)}{2}+(i-1+n-j)g(n-3)\right] $$

预处理 $f,g,h$，树状数组即可。

复杂度 $O(n\log n)$。