求长度为 \(n\) 的逆序对数为 \(k\) 的排列的个数。 \(n,k\le 100000\)
Sol:
\(\Theta(n^3)\) 的dp是显然的，或许能多项式优化，不过有更简单的做法。
我们设 \(s_i\) 表示以 \(i\) 为右端点的逆序对个数，显然一组 \(s_i\) 唯一对应一个序列。我们要求 \(s_i\le i-1,\sum s_i=k\)。
考虑容斥，我们假设有 \(i\) 个位置不满足第一个限制，显然 \(i\) 最大是 \(\Theta(\sqrt(k))\) 的。考虑设 \(f_{i,j}\) 表示从 \(1~n\) 中选 \(i\) 个数和为 \(j\) 的方案，直接插板法就能得出答案。我们发现这个状态不太好转移。
考虑这样来枚举选出的集合：维护一个递减数列，每次操作对所有数都加一，操作结束后可以选择是否在末尾增添一个 \(1\)。
再令 \(f_{i,j}\) 表示在末尾增添 \(i\) 次 \(1\) 后和为 \(j\) 的方案数（注意数列里的数不能超过 \(n\)），我们有：
\[f_{i,j}=f_{i,j-i}+f_{i-1,j-i}-f_{i-1,j-n-1} \]#include <bits/stdc++.h>
using namespace std;
const int N = 200005, mod = 1e9 + 7;
int n, k, fac[N], ifac[N];
inline int power(int a, int b) {
int t = 1, y = a, k = b;
while (k) {
if (k & 1) t = (1ll * t * y) % mod;
y = (1ll * y * y) % mod;
k >>= 1;
} return t;
}
inline int C(int n, int m) {
return 1ll * fac[n] * (1ll * ifac[m] * ifac[n - m] % mod) % mod;
}
int f[505][N];
int main() {
cin >> n >> k;
fac[0] = 1; for (int i = 1; i <= n + k; ++i) fac[i] = 1ll * i * fac[i - 1] % mod;
ifac[n + k] = power(fac[n + k], mod - 2);
for (int i = n + k - 1; ~i; --i) ifac[i] = (1ll * (i + 1) * ifac[i + 1]) % mod;
f[0][0] = 1;
for (int i = 1; i <= 500; ++i) {
for (int j = i; j <= k; ++j) {
f[i][j] = f[i][j - i] + f[i - 1][j - i];
if (f[i][j] >= mod) f[i][j] -= mod;
if (j > n) {
f[i][j] -= f[i - 1][j - n - 1];
if (f[i][j] < 0) f[i][j] += mod;
}
}
} int ans = 0;
for (int i = 0; i <= k; ++i) {
int del = 0;
for (int j = 0; j <= 500; ++j) {
if (j & 1) {
del -= f[j][i];
if (del < 0) del += mod;
} else {
del += f[j][i];
if (del >= mod) del -= mod;
}
} ans += 1ll * del * C(n + k - i - 1, n - 1) % mod;
if (ans >= mod) ans -= mod;
} printf("%d\n", ans);
return 0;
}