容易想到 $dp$。$dp_{i,j}$ 表示由1 ~ $i$自然数组成的数列中有多少个逆序对数为 $k$。

容易想到转移式，其中枚举 $l$ 作为贡献：

时间复杂度为 $O(nk^2)$，理论上无法通过，但实测最多运算 $5\times 10^8$ 次，极限通过。

可以用前缀和将时间复杂度优化到 $O(nk)$，这样可以轻松通过本题。

甚至可以用 $MTT$ 将时间复杂度优化到 $O(nlogn)$，但太（wo）复（bu）杂（hui），在此不做详述。

放个 $O(nk^2)$ 的代码，反正luogu上也能过，自己优化去吧。

#include<bits/stdc++.h>
using namespace std;
#define N 1100
const int P=1e4;
int f[N][N];
int main()
{
	int n,k;scanf("%d%d",&n,&k);f[1][0]=1;
	for(int i=1;i<=n;i++)for(int j=0;j<=k;j++)
		for(int l=0;l<=min(i-1,j);l++)f[i][j]=(f[i][j]+f[i-1][j-l])%P;
	printf("%d\n",f[n][k]);
	return 0;
}

#include <cstdio>
#include <iostream>

using namespace std;

int n, k, p = 10000, f[1010][1010];

int main()
{
    scanf("%d%d", &n, &k);
    f[1][0] = 1;//初始条件，1的逆序为0，且只有1个排列
    for (int i = 2; i <= n; i++)
    {
        int sum = 0;
        for (int j = 0; j <= k; j++)
        {
            (sum += f[i - 1][j]) %= p;
            f[i][j] = sum;
            if(j >= i - 1)//如果j - i + 1>=0了，sum的求和区间左端点就>=0
                (((sum -= f[i - 1][j - i + 1]) %= p)+= p) %= p;
        }
    }
    printf("%d\n", f[n][k]);
    return 0;
}