传送门

「魔法少女小圆」题面好评。

虽然第一眼看成了正在补的「Charlotte」

好像这种题挺套路来着，还是我太蒻了。。。

设$a$为糖果的能量，$b$为药片的能量。

求$\sum[a>b]-\sum[b>a]=k$相当于$\sum[a>b]=\dfrac{n+k}{2}$，那么以下的$k$都代表$\dfrac{n+k}{2}$。

先把$a,b$排个序。设$f(i,j)$表示前$i$个$a$，和所有$b$共匹配$j$组（有的$a$可能未匹配），且该$j$组都满足$a>b$。

转移先考虑$a_i$是否匹配。不匹配就是$f(i-1,j)$。

若选一个匹配，前$i-1$个$a$就要匹配$j-1$个。记$cnt_i$为比$a_i$小的$b$的数量。因为我们排过序了，所以前$i-1$个里匹配的$j-1$个一定都来自于前$cnt_i$的$b$。显然$a_i$不能抢占匹配好的$b$，那只有$cnt_i-(j-1)$个$b$可以选。

即$f(i,j)=f(i-1,j)+(cnt_i-j+1)\times f(i-1,j-1)$

对于$f(n,i)$来说，有$n-i$个$a$未匹配，乘上$(n-i)!$就能得到至少$i$个$a>b$的方案数。

那么设$f(i)=f(n,i)\times(n-i)!$，$g(i)$为恰好$i$个$a>b$。

容易发现每个$g(j)$在$f(i)$里出现了$C_j^i$次。

则$f(i)=\sum\limits_{j=i}^nC_j^ig(j)$

二项式反演得：

$g(i)=\sum\limits_{j=i}^n(-1)^{j-i}C_j^if(j)$

答案就是$g(k)$。

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

#define maxn 2005
#define inf 0x3f3f3f3f

const int mod = 1e9 + 9;

using namespace std;

inline int read(){
    int x=0,y=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return y?-x:x;
}
int f[maxn],fac[maxn]={1},inv[maxn],a[maxn],b[maxn];//f滚起来
int INV(int x){return x==1?1:1ll*(mod-mod/x)*INV(mod%x)%mod;}
inline long long pow1(int x){return x&1?-1ll:1ll;}
inline int C(int n,int m){
    return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int main(){
    int n=read(),k=n+read()>>1,p=0,ans=0;
    for(register int i=1;i<=n;++i)a[i]=read();
    for(register int i=1;i<=n;++i)b[i]=read();
    sort(a+1,a+1+n),sort(b+1,b+1+n);
    f[0]=1;
    for(register int i=1;i<=n;++i){
        while(p+1<=n&&b[p+1]<a[i])++p;    
        for(register int j=i;j;--j)
            f[j]=(f[j]+1ll*(p-j+1)*f[j-1]%mod)%mod;
    }
    for(register int i=1;i<=n;++i)fac[i]=1ll*fac[i-1]*i%mod;
    inv[n]=INV(fac[n]);
    for(register int i=n-1;~i;--i)inv[i]=1ll*inv[i+1]*(i+1)%mod;
    for(register int i=k;i<=n;++i)
        (ans+=pow1(i-k)*C(i,k)*f[i]%mod*fac[n-i]%mod)%=mod;
    printf("%d\n",(ans+mod)%mod);
}