BZOJ 3622

直接算 $a_i>b_i$ 对数恰为 $k$ 的不好算

那么可以先算 $a_i>b_i$ 对数至少 $k$ 的

这个排序后随便dp一下就好

那么再除了一下

用 $f_i$ 表示 $a_i>b_i$ 对数至少i的方案数

用 $g_i$ 表示 $a_i>b_i$ 对数恰为i的方案数

那么 $g_i=f_i(n-i)!-\sum_{j=i+1}^n g_jC(j,i)$

其中，$(n-i)!$ 表示除了这 $i$ 个以外的所有元素的排列方式，$g_jC(j,i)$ 表示在 $j$ 个中任取 $i$ 个而多算的方案数

#include<bits/stdc++.h>

using namespace std;

#define rep(i,a,b) for(int i=(a),i##_end=(b);i<=i##_end;++i)

#define For(i,a,b) for(int i=(a),i##_end=(b);i<i##_end;++i)

#define per(i,a,b) for(int i=(b),i##_st=(a);i>=i##_st;--i)

#define fi first

#define se second

#define pb push_back

#define mp make_pair

#define dbg(x) cerr<<#x" = "<<x<<endl

#define debug(...) fprintf(stderr, __VA_ARGS__)

#define Es(x,i) for(Edge *i=G[x];i;i=i->nxt)

typedef long long ll;

typedef pair<int,int> pii;

const int inf=~0u>>1,mod=1e9+9;

char *TT,*mo,but[(1<<15)+2];

#define getchar() ((TT==mo&&(mo=((TT=but)+fread(but,1,1<<15,stdin)),TT==mo))?-1:*TT++)

inline int rd() {

    int x,c,f=1;while(!isdigit(c=getchar()))f=c!='-';x=c-'0';

    while(isdigit(c=getchar()))x=x*10+c-'0';return f?x:-x;

}

inline int pw(int n,int m){int r=1;for(;m;m>>=1,n=(ll)n*n%mod)if(m&1)r=(ll)r*n%mod;return r;}

const int N=2011;

int n,K;

int a[N],b[N];

int f[N][N];

int fac[N],fai[N];

inline int Init(){

	fac[0]=1;

	For(i,1,N)fac[i]=(ll)fac[i-1]*i%mod;

	fai[N-1]=pw(fac[N-1],mod-2);

	per(i,1,N-1)fai[i-1]=(ll)fai[i]*i%mod;

}

inline int C(int n,int m){return n<m?0:(ll)fac[n]*fai[m]%mod*fai[n-m]%mod;}

int g[N];

int main(){

#ifdef flukehn

	freopen("test.txt","r",stdin);

#endif

	n=rd(),K=rd();

	rep(i,1,n)a[i]=rd();

	rep(i,1,n)b[i]=rd();

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

	int t=0;

	f[0][0]=1;

	if(n+K&1){

        cout<<0<<endl;

        return 0;

    }else K=n+K>>1;

	rep(i,1,n){

		while(t<n&&b[t+1]<a[i])++t;

		f[i][0]=1;

		rep(j,1,i)if(t-j+1>=0){

			f[i][j]=(f[i-1][j]+(ll)f[i-1][j-1]*(t-j+1))%mod;

		}

	}

	Init();

	per(i,K,n){

		ll r=(ll)f[n][i]*fac[n-i];

		rep(j,i+1,n)r-=(ll)g[j]*C(j,i)%mod;

		g[i]=(r%mod+mod)%mod;

	}

	cout<<g[K]<<endl;

//	cerr<<clock()<<endl;

}