已经没有什么好害怕的了

题目大意

给定两个长为 nn 的序列 aabb2n2n 个数互不相同),求有多少种匹配方案满足 ai>bia_i > b_i 的组数比 ai<bia_i < b_i 的组数多 kk 个。

1n2,0001 \leqslant n \leqslant 2,000

题目链接

已经没有什么好害怕的了 - Luogu 4859

题解

补完魔圆后再看一遍这道题。。。

首先,nn 为奇数时答案为 00

对两个序列排序,定义 next[i]next[i] 表示最大的满足 ai>bja_i > b_jjj,考虑 DP,设 f[i,  j]f[i, \; j] 表示已经考虑了 aa 中前 ii 个数,找到 jjbb 中的数使得这些数均比 aa 中的 ii 个数小的方案数(其余不管),则转移为:

f[i,  j]=f[i1,  j]+f[i1,  j1]×(next[i](j1))f[i,  0]=1(i=1,  2,  3,  n)f[i, \; j] = f[i - 1, \; j] + f[i - 1, \; j - 1] \times (next[i] - (j - 1)) \quad f[i, \; 0] = 1(i = 1, \; 2, \; 3 \dots,\;n)

当然,这不是最终答案,因为在计算 ff 时,剩下的是不管的,所以会重算,我们在减去即可。记 g[n,  i]g[n, \; i] 表示 bb 中正好有 ii 个数比对应的 aa 的值小的匹配数,有:

g[n,  i]=f[n,  i]×(ni)!j=i+1ng[n,  j](ji)g[n, \; i] = f[n, \; i] \times (n - i)! - \sum_{j = i + 1}^{n} g[n, \; j] * \binom{j}{i}

计算时,对于每一个 jj,我们减去有 jj 个数小的答案却被记入 ii 个数中的个数,也就是在正好 jj 个数中选 ii 个继续匹配的个数。

代码

由于我们只需计算 g[n,  i]g[n, \; i],故数组 gg 只需一维。

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
#include <cstdio>
#include <algorithm>
// #define DBG
const int MAXN = 2005;
const int MOD = 1e9 + 9;
int a[MAXN], b[MAXN], next[MAXN];
long long fac[MAXN], combin[MAXN][MAXN];
void calc(int n) {
fac[0] = 1;
for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % MOD;
for (int i = 0; i <= n; i++) {
combin[i][0] = 1;
for (int j = 1; j <= i; j++)
combin[i][j] = (combin[i - 1][j] + combin[i - 1][j - 1]) % MOD;
}
}
long long f[MAXN][MAXN];
void dp(int n) {
f[0][0] = 1;
for (int i = 1; i <= n; i++) {
f[i][0] = 1;
for (int j = 1; j <= i; j++)
f[i][j] = (f[i - 1][j] +
f[i - 1][j - 1] * std::max(next[i] - j + 1, 0)) % MOD;
}
}
int main() {
int n, k;
scanf("%d %d", &n, &k);
if ((n + k) & 1) {
puts("0");
return 0;
}
int s = (n + k) >> 1;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
std::sort(a + 1, a + n + 1);
std::sort(b + 1, b + n + 1);
for (int i = 1, j = 1; i <= n; i++) {
while (j <= n && a[i] > b[j]) j++;
next[i] = j - 1;
}
#ifdef DBG
puts("next :");
for (int i = 1; i <= n; i++) printf(" %d", next[i]);
puts("");
#endif
dp(n);
#ifdef DBG
puts("dp - f :");
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= i; j++) printf("f[%d][%d] = %lld ", i, j, f[i][j]);
puts("");
}
#endif
calc(n);
static long long g[MAXN];
for (int i = n; i >= s; i--) {
g[i] = f[n][i] * fac[n - i] % MOD;
for (int j = i + 1; j <= n; j++)
g[i] = (g[i] + MOD - g[j] * combin[j][i] % MOD) % MOD;
#ifdef DBG
printf("g[%d] = %lld\n", i, g[i]);
#endif
}
printf("%lld\n", g[s]);
return 0;
}