逆序对数

题解

求 $n$ 个数的排列中逆序数为 $k$ 的排列数
$f[n][k]$ 表示 $n$ 个数的排列中逆序数为 $k$ 的排列数
$f[n][k] = \sum_{i = 0}^{n - 1} f[n - 1][k - i]$
考虑当前 $n - 1$ 的排列中有 $k - i$ 个逆序对
那么对于 $n$ 的排列，把最大数放到倒数第 $i$ 个数前，就会增加 $i$ 个逆序对
同理 $f[n][k - 1] = \sum_{i = 0} ^ {n - 1} f[n - 1][k - 1 - i]$
两式相减

$$\begin{array}{l} f[n][k] - f[n][k - 1] \\ = \sum_{i = 0}^{n - 1} f[n - 1][k - i] - \sum_{i = 0} ^ {n - 1} f[n - 1][k - 1 - i] \\ = f[n - 1][k] - f[n - 1][k - n] \end{array}$$

then 递推公式为
$f[n][k] = f[n][k - 1] + f[n - 1][k] - f[n - 1][k - n]$