已经没有什么好害怕的了

发表于2017-04-10更新于2020-08-06

题目大意

给定两个长为 nn 的序列 aa 和 bb（2n2n 个数互不相同），求有多少种匹配方案满足 ai>bia_i > b_i 的组数比 ai<bia_i < b_i 的组数多 kk 个。

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

题目链接

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

题解

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

首先，nn 为奇数时答案为 00。

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

f[i,  j]=f[i−1,  j]+f[i−1,  j−1]×(next[i]−(j−1))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]×(n−i)!−∑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;
}