BZOJ 3622
题意：给出 $n$ 个数 $a_i$，以及 $n$ 个数 $b_i$，要求两两配对使得 a > b 的对数减去 a < b 的对数等于 $k$ 。保证 $a,b$ 无相同元素。
我们可以计算出a > b的对数，我们可以算出他是$\frac{k+n}{2}$，方便起见我们让$k=\frac{k+n}{2}$
如果前面的式子不能整除则无解
然后我们考虑容斥，将$a,b$从小到大排序，我们可以设$f(i,j)$为前$i$个位置有$j$对a > b，其他的没有考虑的方案数。
注意这里$f(n,k)$不是答案，因为没有考虑其他的位置
设$l_i$ 为$a_i \geq b_j$的最大$j$，则有转移方程
$$
f(i,j)=f(i-1,j)+f(i-1,j-1)\times (l_i-j+1)
$$
$l_i$相当于当前$i$的所有决策点，这些点一定包括之前的$i$的所有决策点，所以减去$j-1$就可以保证不重复。
然后我们将其他位置安排下来，设$F(i)=f(n, i) \times (n-i)!$
设最后的答案为$g(i)$，则$g(i)$对每个小于$i$的$F$有贡献。
则
$$
F(i)= \sum \limits_{j=i}^{n} C^{i}_{j} \times g(j)
$$
根据二项式反演，则有
$$
g(i)= \sum \limits_{j=i}^{n} (-1)^{j-i} \times C^{i}_{j} \times F(j)
$$
//==========================Head files==========================
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#include<set>
#include<iostream>
#include<map>
#define LL long long
#define db double
#define mp make_pair
#define pr pair<int, int>
#define fir first
#define sec second
#define pb push_back
#define ms(i, j) memset(i, j, sizeof i)
using namespace std;
//==========================Templates==========================
inline int read() {
int x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9'){if (c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9'){x = x * 10 + c - '0'; c = getchar();}
return x * f;
}
inline LL readl() {
LL x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9'){if (c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9'){x = x * 10 + c - '0'; c = getchar();}
return x * f;
}
int power(int a, int b) {
int ans = 1;
while (b) {
if(b & 1) ans = ans * a;
b >>= 1; a = a * a;
}
return ans;
}
int power_mod(int a, int b, int mod) {
a %= mod;
int ans = 1;
while (b) {
if(b & 1) ans = (ans * a) % mod;
b >>= 1, a = (a * a) % mod;
}
return ans;
}
LL powerl(LL a, LL b) {
LL ans = 1ll;
while (b) {
if(b & 1ll) ans = ans * a;
b >>= 1ll;a = a * a;
}
return ans;
}
LL power_modl(LL a, LL b, LL mod) {
a %= mod;
LL ans = 1ll;
while (b) {
if(b & 1ll) ans = (ans * a) % mod;
b >>= 1ll, a = (a * a) % mod;
}
return ans;
}
LL gcdl(LL a, LL b) {return b == 0 ? a : gcdl(b, a % b);}
LL abssl(LL a) {return a > 0 ? a : -a;}
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}
int abss(int a) {return a > 0 ? a : -a;}
//==========================Main body==========================
#define LD "%I64d"
#define D "%d"
#define pt printf
#define sn scanf
#define pty printf("YES\n")
#define ptn printf("NO\n")
//==========================Code here==========================
const LL MAXN = 2000 + 5;
const LL MO = 1e9 + 9;
LL n, k, jc[MAXN], jc_inv[MAXN];
LL a[MAXN], b[MAXN], f[MAXN][MAXN], F[MAXN], g[MAXN];
LL C(LL n, LL m) {
if (m > n) return 0;
return jc[n] * jc_inv[m] % MO * jc_inv[n - m] % MO;
}
int main() {
cin >> n >> k;
if ((n + k) % 2 == 1) return puts("0"), 0;
k = (n + k) >> 1;
for (LL i = 1; i <= n; ++i) scanf("%lld", &a[i]);
for (LL i = 1; i <= n; ++i) scanf("%lld", &b[i]);
sort(a + 1, a + 1 + n), sort(b + 1, b + 1 + n);
jc[0] = 1;
for (LL i = 1; i <= n; ++i) jc[i] = jc[i - 1] * i % MO;
jc_inv[0] = 1;
for (LL i = 1; i <= n; ++i) jc_inv[i] = power_modl(jc[i], MO - 2, MO);
ms(f, 0);
f[0][0] = 1;
for (LL i = 1; i <= n; ++i) {
for (LL j = 0; j <= i; ++j) {
LL li = lower_bound(b + 1, b + 1 + n, a[i]) - b - 1;
if (j != 0) f[i][j] = (f[i][j] + f[i - 1][j - 1] * (li - j + 1) % MO) % MO;
f[i][j] = (f[i][j] + f[i - 1][j]) % MO;
}
}
for (LL i = 1; i <= n; ++i) F[i] = f[n][i] * jc[n - i] % MO;
LL ans = 0, gg = 1;
for (LL i = k; i <= n; ++i) {
ans = (ans + gg * C(i, k) % MO * F[i] % MO) % MO;
gg = (gg * -1) % MO;
gg = (gg + MO) % MO;
}
cout << ans;
return 0;
}
