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

Description

Input

Output

Sample Input

4 2

5 35 15 45

40 20 10 30

Sample Output

4
HINT

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

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

Source

2014湖北省队互测week2

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 2010
#define P 1000000009
#define GET (ch>='0'&&ch<='9')
#define LL long long
using namespace std;
int n,k;
int a[MAXN],b[MAXN],t[MAXN];
LL C[MAXN][MAXN],fac[MAXN],f[MAXN][MAXN],g[MAXN];
void in(int &x)
{
    char ch=getchar();x=0;
    while (!GET)    ch=getchar();
    while (GET) x=x*10+ch-'0',ch=getchar();
}
int main()
{
    in(n);in(k);int j;
    if ((n+k)&1)    return puts("0"),0;
    for (int i=1;i<=n;i++)  in(a[i]);sort(a+1,a+n+1);
    for (int i=1;i<=n;i++)  in(b[i]);sort(b+1,b+n+1);
    for (int i=1;i<=n;i++)  t[i]=lower_bound(b+1,b+n+1,a[i])-b-1;
    C[0][0]=1;
    for (int i=1;i<=n;i++)  for (C[i][0]=1,j=1;j<=i;j++)    C[i][j]=(C[i-1][j-1]+C[i-1][j])%P;
    for (int i=1;i<=n;i++)  fac[i]=(i==1?1:fac[i-1]*i%P);
    f[0][0]=f[1][0]=1;
    for (int i=1;i<=n;i++)  for (f[i][0]=1,j=1;j<=i;j++)
        f[i][j]=(f[i-1][j]+f[i-1][j-1]*max(t[i]-j+1,0))%P;
    for (int i=n;i>=(n+k)>>1;i--)
    {
        g[i]=f[n][i]*fac[n-i]%P;
        for (j=i+1;j<=n;j++)    ((g[i]-=g[j]*C[j][i]%P)+=P)%=P;
    }
    cout<<g[(n+k)>>1];
}