考虑一下插⼊法

$n<=100$

$f[i][j]$表⽰$1$~$i$的全排列有j个逆序对的⽅案数

$f[i][j]=\Sigma f[i-1][j-k](0<=k<=i-1)$

O(m∗n2)O(m*n^2)O(m∗n2)

拓展：如果$n<=1000$呢？

$n<=1000$?

$f[i][j]$是$f[i-1]$中连续⼀段的和

前缀和优化

$O(n\ast m)$

下面上非拓展的代码：

#include
    
     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;}