题解

求$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;
}