f[i][j]表示前i个数，逆序对数为j的答案

则DP方程为：

f[1][0] = 1;    for(i = 2; i <= n; i++)        for(j = 0; j <= m; j++)            for(k = j; k < j + i; k++)                f[i][k] = (f[i][k] + f[i - 1][j]) % p;

但是会超时

所以搞个前缀和优化一下

#include 
     
      #include 
      
       #define N 2001#define p 10000int n, m;int f[N][N], sum[N][N];inline int read(){	int x = 0, f = 1;	char ch = getchar();	for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;	for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';	return x * f;}int main(){	int i, j, k;	n = read();	m = read();	f[1][0] = 1;	for(i = 0; i <= m; i++) sum[1][i] = 1;	for(i = 2; i <= n; i++)		for(j = 0; j <= m; j++)		{			if(j - i + 1 > 0)				f[i][j] = (f[i][j] + ((sum[i - 1][j] - sum[i - 1][j - i]) % p + p) % p) % p;			else				f[i][j] = (f[i][j] + sum[i - 1][j]) % p;			sum[i][j] = (sum[i][j - 1] + f[i][j]) % p;		}	printf("%d\n", f[n][m]);	return 0;}