题目大意

在一个长度为 $n$ 的排列中找出逆序对数量恰好为 $c$ 的排列总数，其中 $1\le n \le 10^3,1\le c \le 10^4$。

思路

考虑将 $1$ 到 $n$ 这些数从小到大一次填进去，因为每一次填入的数多是最大的，所以逆序对增加的数量只与其所在的位置相关，所以设计 $f_{i,j}$ 表示前 $i$ 个数逆序对为 $j$ 的方案数。

在填入第 $i$ 个数时因为前面的 $1$ 到 $i-1$ 都小于 $i$，所以 $i$ 每向前移动一个位置，逆序对的数量就会增加 $1$。

因为 $i$ 的位置并没有限制，所以 $f_{i,j}=\sum \limits^{i-1}\limits_{k=0} f_{i-1,j-k}$。

这个方法的时间复杂度与空间复杂度都是 $O(n\times c^2)$ 的，无法通过此题，所以可以使用前缀和与滚动数组优化。

AC Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e4+5,mod=1e9+7;
int n,c,f[N],ans;
signed main(){
    cin>>n>>c;
	f[0]=1;
    for(int i=1;i<=n;i++){
    	for(int j=1;j<=c;j++) f[j]=(f[j]+f[j-1])%mod;
        for(int j=c;j>=i;j--){
            f[j]=(f[j]-f[j-i]+mod)%mod;
        }
    }cout<<f[c]<<endl;
    return 0;
}