[BZOJ3622]已经没有什么好害怕的了：DP+容斥原理

分析

说白了就是一道先DP再二项式反演的水题，然后被脑残博主把“多\(k\)组”看成了“糖果比药片能量大的组数恰好为\(k\)组”，还改了各种奇怪的地方，最后看了别人的题解才突然意识到这一点。

看来博主离退役不远了，快把我拖走吧没救了没救了。

代码

#include <bits/stdc++.h>

#define rin(i,a,b) for(register int i=(a);i<=(b);++i)

#define irin(i,a,b) for(register int i=(a);i>=(b);--i)

#define trav(i,a) for(register int i=head[a];i;i=e[i].nxt)

typedef long long LL;

using std::cin;

using std::cout;

using std::endl;

inline int read(){

	int x=0,f=1;char ch=getchar();

	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}

	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}

	return x*f;

}

const int MAXN=2005;

const LL MOD=1e9+9;

int n,k,a[MAXN],b[MAXN];

LL c[MAXN][MAXN],f[MAXN][MAXN],fac[MAXN];

void init(){

	c[0][0]=1;

	rin(i,1,n){

		rin(j,0,i){

			c[i][j]=c[i-1][j];

			if(j) c[i][j]=(c[i][j]+c[i-1][j-1])%MOD;

		}

	}

	fac[0]=1;

	rin(i,1,n) fac[i]=fac[i-1]*i%MOD;

}

int main(){

	n=read(),k=read();

	if((n+k)%2){

		printf("0\n");

		return 0;

	}

	k=(n+k)/2;

	init();

	rin(i,1,n) a[i]=read();

	rin(i,1,n) b[i]=read();

	std::sort(a+1,a+n+1);

	std::sort(b+1,b+n+1);

	f[0][0]=1;int cnt=0;

	rin(i,1,n){

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

		rin(j,0,std::min(i,cnt)){

			f[i][j]=f[i-1][j];

			if(j) f[i][j]=(f[i][j]+f[i-1][j-1]*(cnt-(j-1)))%MOD;

		}

	}

	int sgn=-1;LL ans=0;

	rin(i,k,n){

		sgn=-sgn;

		ans=(ans+sgn*c[i][k]*f[n][i]%MOD*fac[n-i]%MOD+MOD)%MOD;

	}

	printf("%lld\n",ans);

	return 0;

}