# [BZOJ3622]已经没有什么好害怕的了-容斥原理-二项式反演

xiaoxiao2021-02-28  7

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

### Sample Input

4 2 5 35 15 45 40 20 10 30

4

### HINT

f[i][j]=(f[i1][j]+f[i1][j1]max(0,c[i]j+1)

#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> using namespace std; typedef long long ll; const int N=2009; const int md=1e9+9; inline int read() { int x=0;char ch=getchar(); while(ch<'0' || '9'<ch)ch=getchar(); while('0'<=ch && ch<='9')x=x*10+(ch^48),ch=getchar(); return x; } int n,k,a[N],b[N],c[N]; ll f[2][N],fac[N],inv[N]; inline ll qpow(ll a,ll b) { ll ret=1; while(b) { if(b&1) ret=ret*a%md; a=a*a%md; b>>=1; } return ret; } inline ll co(ll a,ll b){return fac[a]*inv[b]%md*inv[a-b]%md;} inline ll maxx(ll a,ll b){if(a>b)return a;return b;} inline ll chk(ll &a){if(a>=md)a-=md;} int main() { n=read();k=read(); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<=n;i++) b[i]=read(); sort(a+1,a+n+1); sort(b+1,b+n+1); for(int i=1,j=0;i<=n;i++,c[i]=c[i-1]) while(c[i]<n && b[c[i]+1]<a[i])c[i]++; f[0][0]=1; for(int i=1;i<=n;i++) for(int j=0;j<=c[i];j++) chk(f[i&1][j]=(f[i&1^1][j]+f[i&1^1][j-1]*maxx(0,(ll)c[i]-j+1ll)%md)); fac[0]=1; for(ll i=1;i<=n;i++) fac[i]=fac[i-1]*i%md; inv[n]=qpow(fac[n],md-2); for(ll i=n;i>=1;i--) inv[i-1]=inv[i]*i%md; int s=(n+k)>>1; ll ans=0; for(int i=s;i<=n;i++) (ans+=((i-s)&1?(md-1):1)*co(i,s)%md*f[n&1][i]%md*fac[n-i]%md)%=md; printf("%lld\n",ans); return 0; }