bzoj 3622 已经没有什么好害怕的了

3622: 已经没有什么好害怕的了

Time Limit: 10 Sec  

Memory Limit: 256 MB

Submit: 805  

Solved: 377

[Submit][Status][Discuss]

Description

Input

Output

Sample Input

4 2
5 35 15 45
40 20 10 30

Sample Output

4

HINT

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

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

Source

2014湖北省队互测week2

【分析】

组合数+dp

【代码】

//bzoj 3622 已经没有什么好害怕的了
#include<bits/stdc++.h>
#define N 2000
#define ll long long
#define fo(i,j,k) for(i=j;i<=k;i++)
using namespace std;
const int mod=1e9+9;
const int mxn=2005;
int n,k;
int a[mxn],b[mxn];
int dp[mxn][mxn],ans[mxn];
int fac[mxn],inv[mxn],num[mxn];
inline void init()
{
    int i,j;
    fac[0]=inv[0]=inv[1]=1;
    fo(i,1,N) fac[i]=(ll)fac[i-1]*i%mod;
    fo(i,2,N) inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;
    fo(i,1,N) inv[i]=(ll)inv[i]*inv[i-1]%mod;
}
inline int C(int n,int m)
{
    if(n<m) return 0;
    return (ll)fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int main()
{
    int i,j;
    init();
    scanf("%d%d",&n,&k);
    if((n+k)%2==1)
      return puts("0"),0;
    k=n+k>>1;
    fo(i,1,n) scanf("%d",&a[i]);
    fo(i,1,n) scanf("%d",&b[i]);
    sort(a+1,a+n+1),sort(b+1,b+n+1);
    for(j=0,i=1;i<=n;i++)
    {
        while(j<n && b[j+1]<a[i]) j++;
        num[i]=j;
    }
    fo(i,0,n) dp[i][0]=1;
    fo(i,1,n) fo(j,1,i)
      dp[i][j]=(dp[i-1][j]+(ll)dp[i-1][j-1]*max(0,num[i]-j+1)%mod)%mod;
    for(i=n;i>=1;i--)
    {
        ans[i]=(ll)dp[n][i]*fac[n-i]%mod;
        fo(j,i+1,n)
          ans[i]=(ans[i]-(ll)C(j,i)*ans[j]%mod)%mod;
        ans[i]=(ans[i]+mod)%mod;
    }
    printf("%d\n",ans[k]%mod);
    return 0;
}