自动搬运

查看原文

来自洛谷，原作者为

	fjzzq2002 **

搬运于2025-08-24 21:51:28，当前版本为作者最后更新于2017-03-19 22:04:17，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

考虑将一个排列$p_1, p_2 ... p_n$转化到一个容易枚举，容易比较大小的序列上。

对于每个$1 \leq x \leq n$，设$0 \leq a_x \leq n-x$，表示有多少个$y>x$满足$p_y>p_x$。

有了这个序列，我们可以从后往前逐项推出原排列，同时我们可以发现逆序对个数即为$\sum a_x$，并且p的字典序即为a的字典序，证明略。

考虑逐位确定a，那么我们只需记$f[i][j]$表示$a_i ... a_n$的和为j的方案数，前缀和优化dp，dp完逐位确定即可。

因为$f[i][j]$可能会爆long long，我们对于大于$10^{13}$的数就直接取$10^{13}+1$即可。

复杂度$O(n^3)$，开数组时需要小心爆空间。