Description：

求 $n$ 的排列中逆序对数为 $k$ 的排列有多少个。

$1\le n,k\le 1000$

Solution：

看题目和数据范围应该是一个 $O(nk)$ 的计数 $DP$ ，根据排列计数的套路，设 $f[i][j]$ 表示 $i$ 的排列逆序对数为 $j$ 的有多少个，然后看新加进去的数 $i+1$ 放在原排列的什么位置，对 $j$ 有什么影响，发现新增一个这个数只可能会产生 $[0,min(i,j)]$ 的逆序对数的贡献，于是得到了转移方程 $\begin{align}f[i][j]=\sum_{k=0}^{\min(i-1,j)} f[i-1][j-k]\end{align}$ ，这样转移是 $O(n^2k)$ 的，这时候有两种可能，一是可以优化，二是状态或者转移错了而无法优化。后面的 $k$ 与状态无关且连续，这时可以考虑前缀和优化，把式子变一下形： $\begin{align}f[i][j]=\sum_{k=j-\min(i-1,j)}^j f[i-1][k]\end{align}$ ，就可以前缀和优化了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 1050

#define MOD 10000

int f[MAXN][MAXN];

int sum[MAXN][MAXN];

int main()

{

	scanf("%d%d",&n,&m);

	f[0][0] = 1;sum[0][0] = 1;

	for(int i = 1;i <= m;++i)sum[0][i] = 1;

	for(int i = 1;i <= n;++i)

	{

		for(int j = 0;j <= m;++j)

		{

			f[i][j] = sum[i - 1][j];

			if(j - min(i - 1,j) >= 1)f[i][j] = (f[i][j] - sum[i - 1][j - min(i - 1,j) - 1] + MOD) % MOD;

			if(j != 0)sum[i][j] = (sum[i][j - 1] + f[i][j]) % MOD;

			else sum[i][j] = f[i][j];

		}

	}

	cout << f[n][m] << endl;

	return 0;

}