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

Posted on | Edited on | In , | Views:

题目链接

[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;
}