听说是套路我不会的容斥+DP题.

Description

给定长度为 $N$ 的数组 $a[],b[]$.

要把它们配对起来，使得恰好有 $K$ 对满足 $a[i]>b[ P[i] ]$，求方案数.

$N \le 2000$.

Solution

首先, 列个方程是可以求出到底要多少对满足条件的配对.

那么接下来就考虑怎么求出恰好$k$对. 我们先放宽条件, 求至少$k$对的方案, 最后用一个二项式容斥系数即可. 证明见CQZhangYu的博客.

下面是DP. 对于一个状态$f_{i,j}$, 糖果做到$i$, 有至少$k$对满足条件. 将两个数组排序, 我们可以预处理出对于糖果$i$最大的位置$p$, 满足$a_i > b_p$. 那么有转移:

$f[i][j] = f[i- 1][j] + f[i-1][j-1] \times (p - j + 1)$.

我们在最后一个系数中可以减去被重复计数的部分.

???

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
#include <bits/stdc++.h>
#define mod 1000000009

using namespace std;
typedef long long ll;

const int maxn = 2005;

int n, k, a[maxn], b[maxn], p[maxn];
ll c[maxn][maxn], f[maxn][maxn], fac[maxn];

void init() {
  c[0][0] = 1;
  for (int i = 1; i <= n; ++i) {
    c[i][0] = 1;
    for (int j = 1; j <= i; ++j)
      c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
  }
  fac[0] = 1;
  for (int i = 1; i <= n; ++i)
    fac[i] = (fac[i - 1] * i) % mod;
}

int main() {
  scanf("%d%d", &n, &k);
  if ((n ^ k) & 1) {
    puts("0");
    return 0;
  }
  k = ((n + k) >> 1);
  init();
  for (int i = 1; i <= n; ++i)
    scanf("%d", &a[i]);
  for (int i = 1; i <= n; ++i)
    scanf("%d", &b[i]);
  sort(a + 1, a + 1 + n);
  sort(b + 1, b + 1 + n);
  f[0][0] = 1;
  for (int i = 1; i <= n; ++i) {
    int k = 1;
    for (; k <= n && b[k] < a[i]; ++k);
    --k;
    for (int j = 1; j <= i; ++j)
      f[i][j] = (f[i - 1][j] + f[i - 1][j - 1] * max(k - j + 1, 0) % mod) % mod;
    f[i][0] = f[i - 1][0];
  }
  ll coe = 1, ans = 0;
  for (int i = k; i <= n; ++i, coe = -coe)
    f[n][i] = f[n][i] * fac[n - i] % mod, 
    ans = (ans + coe * f[n][i] * c[i][k] % mod + mod) % mod;
  printf("%lld\n", (ans + mod) % mod);
  return 0;
}