求 $n$ 个数的排列中逆序数为 $k$ 的排列数

$f[n][k]$ 表示 $n$ 个数的排列中逆序数为 $k$ 的排列数

$f[n][k] = \sum_{i = 0}^{n - 1} f[n - 1][k - i]$

考虑当前 $n - 1$ 的排列中有 $k - i$ 个逆序对

那么对于 $n$ 的排列，把最大数放到倒数第 $i$ 个数前，就会增加 $i$ 个逆序对

同理 $f[n][k - 1] = \sum_{i = 0} ^ {n - 1} f[n - 1][k - 1 - i]$

两式相减

\begin{array}{l}

f[n][k] - f[n][k - 1] \\

= \sum_{i = 0}^{n - 1} f[n - 1][k - i] - \sum_{i = 0} ^ {n - 1} f[n - 1][k - 1 - i] \\

= f[n - 1][k] - f[n - 1][k - n]

\end{array}

then 地推公式为

$f[n][k] = f[n][k - 1] + f[n - 1][k] - f[n - 1][k - n]$

#include 
     
      #define gc getchar()inline int read() {    int x = 0; char c = gc;    while(c < '0' || c > '9') c = gc;    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc;    return x;} int f[(int)1e3 + 10][(int)1e3 + 10];const int Mod = 10000;void Work() {    int n = (int)1e3;    for(int i = 1; i <= n; i ++) f[i][0] = 1;    for(int i = 2; i <= n; i ++) {        for(int j = 1; j <= i * (i - 1) / 2 && j <= (int)1e3; j ++) {            f[i][j] = (f[i][j] + f[i][j - 1] + f[i - 1][j]) % Mod;            if(j - i >= 0) f[i][j] -= f[i - 1][j - i];            f[i][j] = (f[i][j] + Mod) % Mod;        }    }}int main() {    Work();    int T = read();    for(; T; T --) printf("%d\n", f[read()][read()]);    return 0;}