Description

图片略

Solution

对啊，已经没有什么好害怕的了

没有头的麻美学姐还是很萌的（雾

排序预处理p[i]为b中小于a[i]的最大的数的标号

f[i][j]表示前i个糖果使得糖果大于药片的至少有j组

则f[i][j]=f[i-1][j]+f[i-1][j-1]*(p[i]-j+1)

容斥得g[j]=f[n][j]*(n-j)!-∑g[k]*C(j,k) (j+1<=k<=n)

（Update:今天发现这个好像是广义容斥原理？）

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define MAXN 2002#define Mod 1000000009typedef long long LL;using namespace std;int n,k,a[MAXN],b[MAXN],p[MAXN];LL f[MAXN][MAXN],c[MAXN][MAXN],g[MAXN];int read(){    int x=0,f=1;char c=getchar();    while(c<'0'||c>'9'){        if(c=='-')f=-1;c=getchar();    }    while(c>='0'&&c<='9'){        x=x*10+c-'0';c=getchar();    }    return x*f;}int main(){    n=read(),k=read();    if((n+k)%2)    {printf("0");return 0;}    k=(n+k)/2;    for(int i=1;i<=n;i++)    a[i]=read();    for(int i=1;i<=n;i++)    b[i]=read();    sort(a+1,a+1+n);    sort(b+1,b+1+n);    int t=1;    for(int i=1;i<=n;i++)    {        while(a[i]>b[t]&&t<=n)t++;        p[i]=t-1;    }    f[0][0]=1;    for(int i=1;i<=n;i++)    for(int j=0;j<=i;j++)    {        if(j)f[i][j]=(f[i-1][j-1]*max(0,p[i]-j+1))%Mod;        f[i][j]=(f[i][j]+f[i-1][j])%Mod;    }    c[1][0]=1;c[1][1]=1;    for(int i=2;i<=n;i++)    for(int j=0;j<=i;j++)    {
    if(!j)c[i][j]=1;c[i][j]=(c[i-1][j-1]+c[i-1][j])%Mod;}    for(int i=n;i>=k;i--)    {        g[i]=f[n][i];        for(int j=1;j<=n-i;j++)        g[i]=(g[i]*j)%Mod;        for(int j=i+1;j<=n;j++)        {            g[i]=(g[i]-(g[j]*c[j][i])%Mod+Mod)%Mod;        }    }    printf("%d",g[k]);    return 0;}