题目链接：
题意：是中文题。
题解：很显然要设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#include #include #include #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;}