已经没有什么好害怕的了

有糖果和药片各n个。糖果ii有能量ai，药片i有能量bi。

你需要将药片和糖果两两配对，求有多少种方案满足糖果比药片能量大的组数减去药片比糖果能量大的组数恰好为k。
保证所有的能量两两不同，答案对109+9取模。
Input Format#
第一行两个整数n,k
第二行n个整数，表示糖果的能量。
第三行n个整数，表示药片的能量。
Output Format#
输出一行一个整数，表示方案数。

Sample Input#

4 2
5 35 15 45
40 20 10 30
Sample Output#

题意：给定a数组和b数组，大小都为N，现在让你两两配对，使得a>b个个数=(N+K)/2; a<b的个数=(N-K)/2;
思路：

首先判断是否有解，也就是(n+k)/2 mod 2=0
这样的话也就相当于糖比药大的正好有(n+k)/2组
然后剩下的和BZOJ2024就一样了
dp一下f(i,j)表示前i个糖选出了j个并且比配对的药大的方案数
答案就是至少满足k个-至少满足k+1个+至少满足k+2个…
就是容斥一下，
每一次将没选的乘上阶乘（表示任意配对个数），容斥系数是C(i,k)

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
#define Mod 1000000009
#define LL long long
#define N 2005
int n,k,a[N],b[N];
LL ans,mul[N],c[N][N],f[N][N];

int main()
{
scanf("%d%d",&n,&k);
if ((n+k)&1)
{
puts("0");
return 0;
}
k=(n+k)>>1;
mul[0]=1;
for (int i=1;i<=n;++i)
mul[i]=mul[i-1]*(LL)i%Mod;
for (int i=0;i<=n;++i)
c[i][0]=1;
for (int i=1;i<=n;++i)
for (int j=1;j<=n;++j)
c[i][j]=(c[i-1][j]+c[i-1][j-1])%Mod;
for (int i=1;i<=n;++i)
scanf("%d",&a[i]);
for (int i=1;i<=n;++i)
scanf("%d",&b[i]);
sort(a+1,a+n+1);
sort(b+1,b+n+1);
int now=0;
for (int i=0;i<=n;++i)
f[i][0]=1;
for (int i=1;i<=n;++i)
{
while (now<n&&b[now+1]<a[i]) //找到某个最大的位置now,b[now]<a[i]
++now;
for (int j=1;j<=i;++j)
{
f[i][j]=f[i-1][j];
f[i][j]+=f[i-1][j-1]*(now-j+1)%Mod;
f[i][j]%=Mod;
}
}
for (int i=k,opt=1;i<=n;++i,opt=-opt)
{
ans+=f[n][i]*mul[n-i]%Mod*c[i][k]*opt%Mod;
//f[n,i]表示选择好n个物品后，有i个是糖果比药片大的，然后乘上(n-i)!
//就变成了至少有i个是果比药片大的了
//然后套公式进行求解
ans=(ans%Mod+Mod)%Mod;
}
printf("%lld\n",ans);
}

在算强制满足i种条件的情况时，也可以用O(N^2)的办法

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=2005,mod=1000000009;
int n,k,a[N],b[N],jc[N],ijc[N],right[N],f[N][N],g[N];
int fastpow(int a,int x)
{
    int res=1;
    while(x)
	{
        if(x&1)
		{
            res=1LL*res*a%mod;
        }
        x>>=1;
        a=1LL*a*a%mod;
    }
    return res;
}
int C(int n,int m)
{
    return 1LL*jc[n]*ijc[m]%mod*ijc[n-m]%mod;
}
int main(){
    scanf("%d%d",&n,&k);
    if((n+k)&1)
	{
        puts("0");
        return 0;
    }
    k=(n+k)/2;
    jc[0]=ijc[0]=1;
    for(int i=1;i<=n;i++)
	{
        jc[i]=1LL*jc[i-1]*i%mod;
        ijc[i]=fastpow(jc[i],mod-2);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&b[i]);
    }
    sort(a+1,a+n+1);
    sort(b+1,b+n+1);
    for(int i=1,j=0;i<=n;i++)
	{
        while(j<n&&b[j+1]<a[i])
		{
            j++;
        }
        right[i]=j;
    }
    f[0][0]=1;
    for(int i=1;i<=n;i++)
	{
        for(int j=0;j<=i;j++)
		{
            f[i][j]=f[i-1][j];
            if(j)
			{
                f[i][j]=(f[i][j]+1LL*f[i-1][j-1]*(right[i]-(j-1))%mod)%mod;
            }
        }
    }
    for(int i=n;i>=k;i--) 
	//注意使用逆循环因为g[i]=f[n,i]*gc(n-i)-sigma(g[j]*C[j,i] 
	{
        g[i]=1LL*f[n][i]*jc[n-i]%mod;
        //f[n][i]为正好满足i种情况的，乘上jc[n-i]后，就成了至少满足i种情况了 
        //下面再减去不合法的，又变成正好为i种情况了 
        for(int j=i+1;j<=n;j++)
		{
            g[i]=(g[i]-1LL*g[j]*C(j,i)%mod+mod)%mod;
        }
    }
    printf("%d\n",g[k]);
    return 0;
}

已经没有什么好害怕的了

推荐阅读