求有k个逆序对的排列有多少

题目传送门

大致思路

肯定不能计算所有排列的逆序对, $100!$ 肯定超时
发现n排列的k个逆序对可以由 n-1 排列计算得来:
记dp[i][j]为i排列,有j个逆序对的排列个数
假设n-1排列为 ********
那么插入一个n: ********n ,逆序对个数也就是n-1排列原本有的逆序对个数
再比如 *******n* ,逆序对个数也就是n-1排列原本有的逆序对个数 + 1
以此类推,便有

$$dp[i][j]=\sum_{k=1}^{i-1}dp[i-1][j-k](0≤j-k) $$

另外注意初始化

Code

void solve() {
    int n,k;
    cin>>n>>k;
    vector<vector<int> > dp(n+1,vector<int>(n*(n-1)/2+1,0));
    dp[2][1]=1;
    dp[2][0]=1;
    for(int i=3;i<=n;i++) {
        for(int j=0;j<=k;j++) {
            for(int l=0;l<i && j-l>=0;l++) dp[i][j]=(dp[i][j]+dp[i-1][j-l])%10000;
        }
    }
    cout<<dp[n][k]<<el;
}