BZOJ3622 已经没有什么好害怕的了

Description

Input

Output

Sample Input

4 2
5 35 15 45
40 20 10 30

Sample Output

HINT

输入的2*n个数字保证全不相同。

还有输入应该是第二行是糖果，第三行是药片

首先$a_i>b_i$的情况数：

$k=\frac{n+k}{2}$

如果不能整除则无解

先按a,b排序

预处理出$l[i]$，表示$a_i$大于$b_j$的最大j

这样设f[i][j]表示当前a序列第i个数，有j组$a>b$的方案

使$a_i>b$有$l[i]$种方案，但是前面已经用了j-1

所以$f[i][j]=f[i-1][j]+f[i-1][j-1]*(l[i]-j+1)$

这样求出来的是“至少”有j对的方案数，而我们需要的是“恰好”有k对的方案数。

所以容斥

$ans=\sum_{i=k}^{n}(-1)^{i-k}*f[n][i]*C_i^{k}*(n-i)!$

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 typedef long long lol;

 int a[],b[],n,k,Mod=1e9+,l[];

 lol f[][],C[][],fac[],ans;

 int main()

 {int i,j;

   cin>>n>>k;

   if ((n+k)&)

     {

       cout<<;

       return ;

     }

   k=(n+k)/;

   fac[]=;

   for (i=;i<=n;i++)

     fac[i]=1ll*fac[i-]*i%Mod;

   for (i=;i<=n;i++)

     {

       C[i][]=;

       for (j=;j<=i;j++)

     　　C[i][j]=(C[i-][j-]+C[i-][j])%Mod;

     }

   for (i=;i<=n;i++)

     {

       scanf("%d",&a[i]);

     }

   for (i=;i<=n;i++)

     {

       scanf("%d",&b[i]);

     }

   sort(a+,a+n+);sort(b+,b+n+);

   for (i=;i<=n;i++)

     {

       for (j=;j<=n;j++)

     　　if (a[i]>b[j]) l[i]++;

     　　else break;

     }

   for (i=;i<=n;i++)

     {

       f[i][]=;

       for (j=;j<=i;j++)

     　　{

       　　f[i][j]=(f[i][j]+1ll*(l[i]-(j-))*f[i-][j-]%Mod)%Mod;

       　　f[i][j]=(f[i][j]+f[i-][j])%Mod;

     　　}

     }

   for (i=k;i<=n;i++)

     {

       if ((i-k)%==)

     　　ans+=1ll*f[n][i]*C[i][k]%Mod*fac[n-i]%Mod,ans%=Mod;

       else ans-=1ll*f[n][i]*C[i][k]%Mod*fac[n-i]%Mod,ans=(ans+Mod)%Mod;

     }

   cout<<ans;

 }

巴特西