因为不存在任意两个数相同，那么设糖果比药片大的组有 (x) 个，药片比糖果大的组有 (y) 个，那么我们有：
[x + y = n, x - y = k
]
即：
[x = frac{n + k}{2}, y = frac{n - k}{2}
]
估本题实质上是问有多少种方案使得糖果比药片大的组恰好有 (frac{n + k}{2}) 个，也就是有 (frac{n + k}{2}) 个糖果匹配了比他小的药片。因为选择的顺序是没有关系的，因此为了能方便的知道当前这个数有多少个比其小的数，我们将药片和糖果分别从小到大排好序，那么糖果更大的一定能选糖果比他小的能选的药片，于是我们可以考虑设计一个 (dp)，令 (dp_{i, j}) 表示当前考虑完了前 (i) 个糖果，有 (j) 个糖果选择了比他小的药片，假设 (cnt_i) 表示比 (i) 号糖果小的药片有多少个，那么有转移：
[dp_{i, j} = (cnt_i - j + 1) dp_{i - 1, j - 1} + dp_{i - 1, j}
]
但是做完这个 (dp) 以后，我们发现 (dp_{n, frac{n + k}{2}}) 并不是答案，因为实际上上面这个 (dp) 只确定了 (frac{n + k}{2}) 个糖果比药片大的组的分组，剩下没有分组的糖果和药片并没有考虑进来，但是剩下的方案我们不能保证其刚好全都是药片比糖果大，因此直接这样计数是行不通的。
思考一下问题所在，剩下的位置可能会存在若干个糖果比药片大的组，而我们此时已经选定了 (frac{n + k}{2}) 个组糖果一定比药片大。这像不像我们二项式反演中钦定一些位置一定合法，而其他位置随意的样子。于是我们可以考虑使用二项式反演解决这个问题。令 (f_i) 表示钦定有 (i) 个组糖果比药片大的方案，那么有：
[f_i = dp_{n, i} imes (n - i)!
]
按照二项式反演的套路再令 (g_i) 表示恰好有 (i) 个组糖果比药片大的方案，那么可以得到 (f, g) 之间的关系：
[f_i = sumlimits_{j = i} ^ n inom{j}{i} g_j
]
则
[g_{frac{n + k}{2}} = sumlimits_{i = frac{n + k}{2}} ^ n (-1) ^ {i - frac{n + k}{2}} dbinom{i}{frac{n + k}{2}} dp_{n, i} imes (n - i)!
]
直接计算即可。
#include<bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for(int i = l; i <= r; ++i)
const int N = 2000 + 5;
const int Mod = 1000000000 + 9;
int n, k, ans, a[N], b[N], f[N], cnt[N], fac[N], C[N][N], dp[N][N];
int read(){
char c; int x = 0, f = 1;
c = getchar();
while(c > '9' || c < '0'){ if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int Inc(int a, int b){
return (a += b) >= Mod ? a - Mod : a;
}
int Dec(int a, int b){
return (a -= b) < 0 ? a + Mod : a;
}
int Mul(int a, int b){
return 1ll * a * b % Mod;
}
int main(){
n = read(), k = read();
rep(i, 1, n) a[i] = read();
rep(i, 1, n) b[i] = read();
sort(a + 1, a + n + 1), sort(b + 1, b + n + 1);
rep(i, 1, n){
if(b[n] <= a[i]){ cnt[i] = n; continue;}
rep(j, 1, n) if(b[j] > a[i]){ cnt[i] = j - 1; break;}
}
fac[0] = C[0][0] = 1;
rep(i, 1, n) fac[i] = Mul(fac[i - 1], i), C[i][0] = 1;
rep(i, 1, n) rep(j, 1, i) C[i][j] = Inc(C[i - 1][j - 1], C[i - 1][j]);
dp[0][0] = 1;
rep(i, 1, n) rep(j, 0, min(i, cnt[i])){
dp[i][j] = dp[i - 1][j];
if(j) dp[i][j] = Inc(dp[i][j], Mul(dp[i - 1][j - 1], cnt[i] - j + 1));
}
rep(i, 0, n) f[i] = Mul(dp[n][i], fac[n - i]);
rep(i, (n + k) / 2, n){
if((i + (n + k) / 2) & 1) ans = Dec(ans, Mul(C[i][(n + k) / 2], f[i]));
else ans = Inc(ans, Mul(C[i][(n + k) / 2], f[i]));
}
printf("%d", ans);
return 0;
}