【题目描述】
对于一个数列$a$,如果有$a_i>a_j$且$i<j$,那么我们称$a_i$与$a_j$为一对逆序对数。若对于任意一个由$1\sim n$自然数组成的数列,可以很容易求出有多少个逆序对数。那么逆序对数为$k$的这样自然数数列到底有多少个?

【输入格式】
第一行为两个整数$n,k$。

【输出格式】
写入一个整数,表示符合条件的数列个数,由于这个数可能很大,你只需输出该数对$10000$求余数后的结果。

题解

挺水的吧。。。简单推一下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, 5000ll); 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;
}

评论