题解 P3672 【小清新签到题】

· · 题解

考虑将一个排列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)，开数组时需要小心爆空间。