BZOJ3622（容斥+dp）
思路[*]“恰k个”考虑求至少k、k+1……个容斥
[*]题面说所有数字都不同，可以将所求转化为糖比药多的组数恰为\((n+k)/2\)的方案数
[*]\(f\)数组我觉得更好的理解方式是"前i个已经安排了j组糖大于药、别的先没管"的方案数
[*]\(f*(n-i)!\)即为把其它的安排了以后的方案数，但是这里面有重的
[*]设\(g\)为恰i个的方案数。$$g=f*(n-i)!-\sum_{j=i+1}ng*C_ji$$要说为什么又去重又剪掉不合法了，我也不通透，目前只是已知这样做是对的话那直观感受一下应该对吧……
#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, b;
ll f, g;
ll fac, C;
int READ() {
scanf("%d %d", &n, &k);
for (int i = 1; i <= n; i++)
scanf("%d", &a);
for (int i = 1; i <= n; i++)
scanf("%d", &b);
m = (n + k) / 2;
return (n + k) % 2;
}
void PRE() {
sort(a + 1, a + 1 + n);
sort(b + 1, b + 1 + n);
fac = 1;
for (int i = 1; i <= n; i++)
fac = fac * i % mod;
for (int i = 0; i <= n; i++) {
C = 1;
for (int j = 1; j <= i; j++)
C = (C + C) % mod;
}
}
void DP() {
for (int i = 0; i <= n; i++)
f = 1;
for (int i = 1, p = 0; i <= n; i++) {
for (; p < n && b < a; p++);
for (int j = 1; j <= i; j++) {
f = (f * max(0, p - j + 1) % mod + f) % mod;
}
}
for (int i = n; i >= m; i--) {
g = f * fac % mod;
for (int j = i + 1; j <= n; j++) {
g = (g - g * C % mod) % mod;
}
}
ans = (g + mod) % mod;
}
int main() {
if (READ() == 1) {
return !printf("0\n");
}
PRE();
DP();
return !printf("%d\n", ans);
}
文档来源：51CTO技术博客https://blog.51cto.com/u_14696602/3107447
页:
[1]