思路

  • “恰k个”考虑求至少k、k+1……个容斥
  • 题面说所有数字都不同,可以将所求转化为糖比药多的组数恰为\((n+k)/2\)的方案数
  • \(f[i][j]\)数组我觉得更好的理解方式是"前i个已经安排了j组糖大于药、别的先没管"的方案数
  • \(f[n][i]*(n-i)!\)即为把其它的安排了以后的方案数,但是这里面有重的
  • 设\(g[i]\)为恰i个的方案数。$$g[i]=f[n][i]*(n-i)!-\sum_{j=i+1}i$$要说为什么又去重又剪掉不合法了,我也不通透,目前只是已知这样做是对的话那直观感受一下应该对吧……
#include <cstdio>
#include <algorithm>
using namespace std; typedef long long ll;
const int mod = 1e9 + 9;
const int maxn = 2005; int n, k, m, ans;
int a[maxn], b[maxn];
ll f[maxn][maxn], g[maxn];
ll fac[maxn], C[maxn][maxn]; int READ() {
scanf("%d %d", &n, &k);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = 1; i <= n; i++)
scanf("%d", &b[i]);
m = (n + k) / 2;
return (n + k) % 2;
} void PRE() {
sort(a + 1, a + 1 + n);
sort(b + 1, b + 1 + 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++) {
C[i][0] = 1;
for (int j = 1; j <= i; j++)
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
}
} void DP() {
for (int i = 0; i <= n; i++)
f[i][0] = 1;
for (int i = 1, p = 0; i <= n; i++) {
for (; p < n && b[p + 1] < a[i]; p++);
for (int j = 1; j <= i; j++) {
f[i][j] = (f[i - 1][j - 1] * max(0, p - j + 1) % mod + f[i - 1][j]) % mod;
}
}
for (int i = n; i >= m; i--) {
g[i] = f[n][i] * fac[n - i] % mod;
for (int j = i + 1; j <= n; j++) {
g[i] = (g[i] - g[j] * C[j][i] % mod) % mod;
}
}
ans = (g[m] + mod) % mod;
} int main() {
if (READ() == 1) {
return !printf("0\n");
}
PRE();
DP();
return !printf("%d\n", ans);
}
05-23 17:01