考虑一下插⼊法
$n\&lt;=100$n<=100
$f\left[i\right]\left[j\right]$f[i][j]表⽰ $1$1~ $i$i的全排列有j个逆序对的⽅案数
$f\left[i\right]\left[j\right]=\Sigma f[i-1][j-k](0\&lt;=k\&lt;=i-1)$f[i][j]=Σf[i−1][j−k](0<=k<=i−1)
$O(m\ast n^2)$O(m∗n2)

拓展：如果 $n\&lt;=1000$n<=1000呢？

$n\&lt;=1000$n<=1000?
$f\left[i\right]\left[j\right]$f[i][j]是 $f[i-1]$f[i−1]中连续⼀段的和
前缀和优化
$O(n\ast m)$O(n∗m)

下面上非拓展的代码：

#include<cstdio>
using namespace std;
int f[105][6005];
int main()
{
	int n,k;
	scanf("%d%d",&n,&k);
	f[1][0]=1;
	f[2][0]=1;
	f[2][1]=1;
	f[0][0]=1;
	for(int i=3;i<=n;i++)
	{
		for(int j=0;j<=k;j++)
		{
			for(int kk=0;kk<=i-1&&kk<=j;kk++)
			{
				f[i][j]+=f[i-1][j-kk]%10000;
			}
		}
	}
	printf("%d",f[n][k]%10000);
	return 0;
}