纯粹是觉得这件事有意思，想分享一下。

---

我昨天吃饭的时候，想到了一道题：求 $n$ 所有全排列的逆序对个数之和。

我当时想了个 $O(n^3)$ DP，打算第二天做一下。

今天我先是打了个 $O(n!\cdot n^2)$ 的纯暴力，把一到十的数据测了一下。随便上网上搜了一下。

结果居然真的有公式？！

$$n!\cdot \frac{n(n-1)}{4}$$

我当场就震惊了。

随后我去了趟厕所，蹲坑的时候就在想这道题。

想着想着，我想出来了！

对于所有全排列来说，指定两个位置出现的逆序对个数期望为 $\frac{n!}{2}$。乘上位置的方案数 $\frac{n(n-1)}{2}$，不就完了吗？！

又是有收获的一天啊~