【题目描述】
【输入格式】
【输出格式】
题解 挺水的吧。。。简单推一下DP方程
$dp[i][j]$表示$1\sim i$的全排列中逆序对数量为$j$的有多少个
边界：$dp[2][0]=dp[2][1]=1$特别注意$dp[1][0]=1$
下面是转移方程
举个栗子吧：$3,1,2$现在把$4$加进去 如果加在第$k$个数后面$(0\le k\le 3)$逆序对就会多$3-k$个
那就完事啦$dp[i][j]=\sum\limits_{k=0}^{i-1}dp[i-1][j-k]$
就比如推$dp[4][3]$吧$4$在排列第一位，且逆序对数量为$3$的方案数就是$dp[3][0]$因为你把$4$放第一个就一定会多产生$3$个逆序对嘛 那原来$3$个数就只能是没有逆序对了
前缀和$O(1)$转移
$dp$数组第一维可以去掉然后离线做 虽然这个数据很水 不去掉也没事 但是有一年ACM/ICPC好像考了原题 但是卡空间
然后离线给询问从小到大排个序 边DP边存答案 时间复杂度$O(n^2)$
###代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 #include <bits/stdc++.h> using namespace std ;typedef long long ll;inline int read () int x = 0 , f = 1 ; char ch = getchar(); for (; ch > '9' || ch < '0' ; ch = getchar()) if (ch == '-' ) f = -1 ; for (; ch <= '9' && ch >= '0' ; ch = getchar()) x = (x << 3 ) + (x << 1 ) + (ch ^ '0' ); return x * f; } const ll mod = 1000000007 ;int tot, now;ll dp[5005 ], sum[5005 ], ans[5005 ]; struct question { int n, m, ind; } q[5005 ]; inline bool cmp (question a, question b) return a.n < b.n; } inline void DP () dp[0 ] = dp[1 ] = 1 ; for (ll j = 0 ; j <= 5000 ; j++) { sum[j] = j == 0 ? 1 : 2 ; } while (now <= tot && q[now].n == 2 ) { ans[q[now].ind] = dp[q[now].m]; now++; } for (ll i = 3 ; i <= 5000 ; i++) { memset (dp, 0 , sizeof (dp)); for (ll j = 0 ; j <= min(i * (i - 1 ) / 2 , 5000l l); j++) { if (j - i < 0 ) { dp[j] = sum[j]; } else { dp[j] = (sum[j] - sum[j - i] + mod) % mod; } } memset (sum, 0 , sizeof (sum)); sum[0 ] = dp[0 ]; for (ll j = 1 ; j <= 5000 ; j++) { sum[j] = (sum[j-1 ] + dp[j]) % mod; } while (now <= tot && q[now].n == i) { ans[q[now].ind] = dp[q[now].m]; now++; } } } int main () tot = read(); for (int i = 1 , n, m; i <= tot; i++) { n = read(); m = read(); q[i] = question{n, m, i}; } sort(q + 1 , q + tot + 1 , cmp); now = 1 ; while (now <= tot && q[now].n == 1 ) { ans[q[now].ind] = q[now].m == 0 ? 1 : 0 ; now++; } DP(); for (int i = 1 ; i <= tot; i++) { printf ("%lld\n" , ans[i]); } return 0 ; }
