考虑朴素 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}\left[x^k\right]\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
#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;
}