# bzoj 3622 已经没有什么好害怕的了

4 2

5 35 15 45

40 20 10 30

4

### 题解

$f[i][j] += f[i – 1][j]$（不限制第i个要大）
$f[i][j] += f[i – 1][j – 1] \times (p – j)$（限制第i个要大）

$$g[i][j]=f[i][j]\times (i−j)! − \sum_{k = j + 1}^n g[i][k] \times C^i_j$$

#include <cstdio>
#include <algorithm>
using namespace std;
const int mod = 1000000009;
int n, k, ans, a[2010], b[2010], C[2010][2010], mul[2010], f[2010][2010];
main() {
scanf("%d%d", &n, &k);
if ((n + k) & 1)
return 0, puts("0");
k = (n + k) / 2; f[0][0] = 1;
C[0][0] = C[1][0] = 1;
for (int i = 1; i <= 2000; ++i, C[i][0] = 1)
for (int j = 1; j <= i; ++j)
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
mul[0]=1;
for (int i = 1; i <= n; ++i) mul[i] = 1ll * mul[i - 1] * i % mod;
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);
for (int i = 0, p = 0; i <= n; ++i) {
while (b[p + 1] < a[i + 1] && p < n) ++p;
for (int j = 0; j <= i; ++j)
if (f[i][j] != 0) {
f[i + 1][j] = (f[i + 1][j] + f[i][j]) % mod;
if (p - j >= 0)
f[i + 1][j + 1] = (f[i + 1][j + 1] + 1ll * f[i][j] * (p - j) % mod) % mod;
}
}
for (int i = 0; i <= n; ++i) f[n][i] = 1ll * f[n][i] * mul[n - i] % mod;
for (int i = k, dlt = 1; i <= n; ++i, dlt = -dlt)
ans = (ans + 1ll * dlt * C[i][k] * f[n][i] % mod) % mod;
ans = (ans + mod) % mod;
printf("%d\n",ans);
}