P4859

如果不能越级打怪还叫什么主角

#include<bits/stdc++.h>
namespace my_std {
	using namespace std;
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define drep(i,x,y) for (int i=(x);i>=(y);i--)
#define go(x) for (int i=head[x];i;i=edge[i].nxt)
	const long long mod=1e9+9;
	template<typename T>
	inline void read(T& t) {
		t=0;
		char f=0,ch=getchar();
		double d=0.1;
		while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();
		while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar();
		if(ch=='.') {
			ch=getchar();
			while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar();
		}
		t=(f?-t:t);
	}
	template<typename T,typename... Args>
	inline void read(T& t,Args&... args) {
		read(t);
		read(args...);
	}
}
using namespace my_std;
long long ksm(long long x,int y) {
	long long ret=1;
	for (; y; y>>=1,x=x*x%mod) if (y&1) ret=ret*x%mod;
	return ret;
}
long long inv(long long x) {
	return ksm(x,mod-2);
}
long long fac[2020],_fac[2020];
void init() {
	fac[0]=_fac[0]=1;
	rep(i,1,2020-1) _fac[i]=inv(fac[i]=fac[i-1]*i%mod);
}
long long C(int n,int m) {
	return n>=m&&m>=0?fac[n]*_fac[m]%mod*_fac[n-m]%mod:0;
}
int n,K;
int a[2020],b[2020],r[2020];
long long dp[2020][2020],f[2020];
long long ans[2020];
int main() {
	init();
	read(n,K);
	if ((n+K)&1) return puts("0"),0;
	K=(n+K)>>1;
	rep(i,1,n) read(a[i]);
	rep(i,1,n) read(b[i]);
	sort(a+1,a+n+1);
	sort(b+1,b+n+1);
	int c=0;
	rep(i,1,n) {
		while (c<n&&b[c+1]<a[i]) ++c;
		r[i]=c;
	}
	dp[0][0]=1;
	rep(i,1,n)
	rep(j,0,i)
	dp[i][j]=(dp[i-1][j]+(j?1ll*(r[i]-j+1)*dp[i-1][j-1]%mod:0ll))%mod;
	rep(i,0,n) f[i]=dp[n][i]*fac[n-i]%mod;
	drep(i,n,K) {
		ans[i]=f[i];
		rep(j,i+1,n) ans[i]=(ans[i]-ans[j]*C(j,i)%mod+mod)%mod;
	}
	cout<<ans[K];
	return 0;
}