考虑朴素 dp，令 \(f_{i,j}\) 为 \(1\sim i\) 排列有 \(j\) 个逆序对的排列数。有转移方程：

\[f_{i,j}=\sum_{k=0}^{i-1}f_{i-1,j-k} \]

特殊地，我们定义 \(j<0\) 的 \(f_{i,j}\) 为 \(0\)。

定义 \(\displaystyle F_i(x)=\sum_{j=0}^{\infty}f_{i,j}x^j\)，有 \(\displaystyle F_{i}(x)=F_{i-1}(x)\sum_{j=0}^{i-1}x^j\)，所以有：

\[F_{n}(x)=\prod_{i=1}^{n}\sum_{j=0}^{i-1}x^j=\prod_{i=1}^{n}\frac{1-x^i}{1-x}=\frac{\prod_{i=1}^{n}(1-x^i)}{(1-x)^n}=(1-x)^{-n}\prod_{i=1}^{n}(1-x^i) \]

把 \((1-x)^{-n}\) 展开一发，化成 \(\displaystyle \left(\prod_{i=1}^{n}(1-x^i)\right)\left(\sum_{i=0}^{\infty}\binom{i+n-1}{n-1}x^i\right)\)。

\(\displaystyle [x^k]\left(\prod_{i=1}^{n}(1-x^i)\right)\) 显然是 \(\{1,2,3,\cdots,n\}\) 里选若干个不同的数和为 \(k\) 的贡献和（选偶数个数是正贡献，奇数个是负贡献）。

设 \(f_{i,j}\) 是选 \(i\) 个不同的数和为 \(j\) 的方案数，可以将加的数看作一个递增序列，那么有转移方程：

全体加 \(1\)， \(\displaystyle f_{i,j}\gets f_{i,j-i}\)。
全体加 \(1\) 并在最前方添上一个 \(1\)， \(\displaystyle f_{i,j}\gets f_{i-1,j-i}\)。
减去 \(n+1\)， \(\displaystyle f_{i,j}\gets -f_{i-1,j-n-1}\)。

因为 \(\sqrt{2k}\) 个数之和就 \(\geq k\)，所以第一维到 \(\sqrt{2k}\approx450\) 就可以。

然后卷积一下：

\[\begin{aligned}[x^k]\left(\left(\prod_{i=1}^{n}(1-x^i)\right)\left(\sum_{i=0}^{\infty}\binom{i+n-1}{n-1}x^i\right)\right)=\sum_{i=0}^{k}\binom{k-i+n-1}{n-1}\sum_{j=1}^{\sqrt{2k}}(-1)^jf_{j,i}\\=\sum_{i=1}^{\sqrt{2k}}\sum_{j=0}^{k}(-1)^i\binom{k-j+n-1}{n-1}f_{i,j}\end{aligned} \]

Code

测评记录：https://loj.ac/s/1802837

#include <bits/stdc++.h>
using namespace std;
namespace Milkcat {
    typedef long long LL;
    const int N = 2e5 + 5, mod = 1e9 + 7;
    struct Combinations {
	    LL mod, f[N], fac[N], inv[N], Finv[N];
	    void init(LL n, LL pmod) {
	        mod = pmod, inv[1] = 1, fac[0] = Finv[0] = 1;
	        for (int i = 2; i <= n; i ++)
	            inv[i] = ((mod - mod / i) * inv[mod % i]) % mod;
	        for (int i = 1; i <= n; i ++)
	            fac[i] = fac[i - 1] * i % mod, Finv[i] = Finv[i - 1] * inv[i] % mod;
	    }
	    LL operator () (LL n, LL m) {
	        if (m > n) return 0;
	        return fac[n] * Finv[m] % mod * Finv[n - m] % mod;
	    }
	} C;
	LL n, k, ans, f[455][N];
    int main() {
		cin >> n >> k, C.init(2e5, mod), f[0][0] = 1;
		for (int i = 1; i <= 450; i ++)
			for (int j = 0; j <= k; j ++) {
				f[i][j] = (f[i][j - i] + f[i - 1][j - i]) % mod;
				if (j > n) f[i][j] = (f[i][j] - f[i - 1][j - n - 1] + mod) % mod;
			}
		for (int i = 0; i <= 450; i ++)
			for (int j = 0; j <= k; j ++)
				ans = (ans + (i & 1 ? -1 : 1) * C(k - j + n - 1, n - 1) * f[i][j] % mod + mod) % mod;
		cout << ans << '\n';
        return 0;
    }
}
int main() {
//	freopen("prongs.in", "r", stdin);
//	freopen("prongs.out", "w", stdout);
    int T = 1;
    while (T --) Milkcat::main();
    return 0;
}

题解zhengjun p3993 2017

题解表格cqoi 2017

526互联

#6077. 「2017 山东一轮集训 Day7」逆序对题解

Code