题目链接：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1020

题意：是中文题。

题解：很显然要设dp[i][j]表示，i个数有j个逆序对有几种然后就是状态的转移，

dp[i][j]=dp[i-1][max(0,j-(i-1)]+.....+dp[i-1][max(j,(i-1)*(i-2)/2];

还会用到前缀和，还有注意最后结果加mod再膜mod，结果可能会负数。

#include <iostream>#include <cstring>#include <algorithm>#include <cstdio>#define mod 1000000007using namespace std;typedef long long ll;int sum[1000000] , dp[1010][30010];int main() {    int t;    memset(dp , 0 , sizeof(dp));    dp[1][0] = 1;    dp[2][0] = 1 , dp[2][1] = 1 , sum[0] = 1 , sum[1] = 2;    for(int i = 3 ; i <= 1000 ; i++) {        for(int j = 0 ; j <= i * (i - 1) / 2 && j <= 30000 ; j++) {            if(j == 0) {                dp[i][j] = 1;            }            else {                int gg = (i - 2) * (i - 1) / 2;                if(j - (i - 1) <= 0) {                    dp[i][j] = sum[min(gg , j)];                }                else {                    dp[i][j] = sum[min(gg , j)] - sum[j - (i - 1) - 1];                }                dp[i][j] = dp[i][j] % mod;            }        }        for(int j = 0 ; j <= i * (i - 1) / 2 && j <= 30000 ; j++) {            if(j == 0) sum[j] = 1;            else sum[j] = sum[j - 1] % mod + dp[i][j] % mod;            sum[j] = sum[j] % mod;        }    }    scanf("%d" , &t);    while(t--) {        int n , m;        scanf("%d%d" , &n , &m);        printf("%d\n" , (dp[n][m] + mod) % mod);    }    return 0;}

51nod 1020 逆序排列（dp，递推）