[Luogu 4859] 已经没有什么好害怕的了

题目链接

[Luogu 4859] 已经没有什么好害怕的了

做法

用$a$表示药片数组,$b$表示糖果数组,两个数组都先升序排列。
考虑dp,$f_{i,j}$表示前$i$个数中有$j$对$a>b$的方案数,
我们这里认为每个a有两种选择,一是选择一个比他小的b来组成新的一对,二是空着不选择,而不是选择一个比他大的b,一定要注意。
那么根据上面的定义,可以得到dp方程,
由于b是升序,所以对于$a_i$,比它小的b一定是一个前缀,所以$now_i$表示b中比我小的是$[1,now_i]$,因为a也是升序,所以$now_i$一定是单调不降的,我们用一个指针维护即可。
那么dp出$f$之后有什么用呢?
我们用$ans_i$表示最后所有点都有匹配后$a>b$的对数有$i$对的方案数($f$中不是有些还没匹配吗),我们最后要求的就是$ans_\frac{n+k}{2}$
发现$ans$并不好求,定义$g_i$表示最后所有点都有匹配后$a>b$的对数有大于$i$对的方案数,那么我们将a中原先没有匹配的点随意匹配,即
发现$ans_i$对于$g_j$的贡献即为$\binom{i}{j}(i\ge j)$
也就是说

可以二项式反演

直接枚举算出$ans_\frac{n+k}{2}$即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<cstdio>
#include<algorithm>
#include<cctype>
#define N (2005)
#define LL long long
using namespace std;
int n,k,r,ans,d;
int a[N],b[N],f[N][N],C[N][N],g[N],jc[N];
const int P=1000000009;
inline bool cmp(int a,int b){
return a>b;
}
inline int Inc(int a,int b){
return (a+b>=P)?(a+b-P):(a+b);
}
template <typename T> void read(T&t) {
t=0;
bool fl=true;
char p=getchar();
while (!isdigit(p)) {
if (p=='-') fl=false;
p=getchar();
}
do {
(t*=10)+=p-48;p=getchar();
}while (isdigit(p));
if (!fl) t=-t;
}
int main(){
read(n),read(k);
if ((n+k)&1){
puts("0");
return 0;
}
for (int i=1;i<=n;i++) read(a[i]);
for (int i=1;i<=n;i++) read(b[i]);
sort(a+1,a+n+1);
sort(b+1,b+n+1);
f[0][0]=1;
r=0;
for (int i=1;i<=n;i++){
for (;r<n&&b[r+1]<a[i];r++);
for (int j=0;j<=n;j++){
f[i][j]=f[i-1][j];
if (j&&r>=j) f[i][j]=Inc(f[i][j],1ll*f[i-1][j-1]*(r-j+1)%P);
}
}
C[0][0]=1;
for (int i=1;i<=n;i++){
for (int j=1;j<=i;j++) C[i][j]=Inc(C[i-1][j],C[i-1][j-1]);
C[i][0]=1;
}
jc[0]=1;
for (int i=1;i<=n;i++) jc[i]=1ll*jc[i-1]*i%P;
for (int i=0;i<=n;i++) g[i]=1ll*f[n][i]*jc[n-i]%P;
k=(n+k)/2;
d=1;
for (int i=k;i<=n;i++){
ans=Inc(ans,1ll*C[i][k]*g[i]%P*d);
ans=Inc(ans,P);
d=-d;
}
printf("%d",ans);
return 0;
}