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,k}。利用前缀和优化可以做到 O(nk)。

Code

#include<stdio.h>
const int mod=1e9+7;
int dp[105];
int T,n,m;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        dp[0]=1;
        for(int i=1;i<=m;++i)dp[i]=0;
        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\n",dp[m]);
    }
    return 0;
}