Solution

设 dp_{i,j} 表示已经填了 1\sim i 的数，产生了 j 个逆序对的方案。对于第 i 个数，放在第 k 个位置，会产生 i-k 个逆序对，所以有转移：dp_{i,j}=\displaystyle\sum_{k=1}^idp_{i-1,j-(i-k)}。初始化 dp_{0,0}=1，答案为 dp_{n,c}。利用前缀和优化可以做到 O(nc)。

Code

#include<stdio.h>
const int mod=1e9+7;
int dp[10005];
int n,m;
int main(){
    scanf("%d%d",&n,&m);
    dp[0]=1;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j)
            if((dp[j]+=dp[j-1])>=mod)dp[j]-=mod;
        for(int j=m;j>=i;--j)
            if((dp[j]-=dp[j-i])<0)dp[j]+=mod;
    }
    printf("%d",dp[m]);
    return 0;
}