P1521 Count Inversions

We call $(i, j)$ an inversion of $a_1, a_2, \cdots, a_N$ if and only if $i < j$ and $a_i > a_j$. For example, $[2, 4, 1, 3, 5]$ has 3 inversions: $(1, 3), (2, 3), (2, 4)$. Now given $N$ and $K$, find the number of permutations of $1, 2, 3, \cdots, N$ whose number of inversions is exactly $K$. Output that count. For example, when $N = 5$, $K = 3$, there are 15 valid permutations. They are: - [1, 2, 5, 4, 3]. - [1, 3, 4, 5, 2]. - [1, 3, 5, 2, 4]. - [1, 4, 2, 5, 3]. - [1, 4, 3, 2, 5]. - [1, 5, 2, 3, 4]. - [2, 1, 4, 5, 3]. - [2, 1, 5, 3, 4]. - [2, 3, 1, 5, 4]. - [2, 3, 4, 1, 5]. - [2, 4, 1, 3, 5]. - [3, 1, 2, 5, 4]. - [3, 1, 4, 2, 5]. - [3, 2, 1, 4, 5]. - [4, 1, 2, 3, 5].

The first line contains two integers $N$ and $K$.

Output the number of permutations of $1 \cdots N$ whose number of inversions is $K$. To avoid big integer arithmetic, output the result modulo $10000$.

Constraints For all testdata, it is guaranteed that $N \le 100$, $K \le N \times (N - 1) / 2$. Translated by ChatGPT 5