题解
求$1 \sim n$的全排列中逆序对数为$k$的数量
数据范围:$n,k \le 1000$
题解
用$f[i][j]$表示$1 \sim i$的全排列中逆序对数为$j$的数量
考虑将$i$插入$1 \sim i-1$的数列中。因为$i$比该数列中所有数都大,所以$i$放在哪里都能产生贡献,贡献的范围为$i-1$(放在首位)$\sim$ $0$(放在末位),可得状态转移方程$$f[i][j]=\sum_{k=\max(0,j-i+1)}^j f[i-1][k]$$
但是这样$dp$的复杂度为$O(N^3)$,需要进行优化
发现求和被重用很多次,索性维护前缀和,并且让和的位置随着$dp$向右移动
代码:
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1000+10;
const int mod=10000;
int n,k;
int dp[N][N];
int main(){
scanf("%d%d",&n,&k);
dp[1][0]=1;
for(int i=2;i<=n;i++){
int sum=0;
for(int j=0;j<=k;j++){
(sum+=dp[i-1][j])%=mod;
dp[i][j]=sum;
if(j-i+1>=0)
(((sum-=dp[i-1][j-i+1])%=mod)+=mod)%=mod;
}
}
printf("%d",dp[n][k]);
return 0;
}