已经没有什么好害怕的了

whz-lld / 2023-09-05 / 原文

已经没有什么好害怕的了

题意

有 $n$ 个糖果和药片两两配对，求恰好药片比糖果能量大的组数为 $k$ 的方案数。
$1\leq n \leq 2000 , 0\leq k\leq n$

题解

先背包直接求出 $dp_i$ 至少有 $i$ 组的方案数，再容斥一下。需要注意的是因为组数少的也会对组数多的有贡献，$dp_k $ 和 $dp_{k+1}$ 在 $dp_i(i\geq k+2)$ 中占的方案数并不相同，所以不能直接 $dp_k-dp_{k+1}$ 。而应该容斥一下，答案为 $\sum_{i=k}^n dp_i\times(-1)^{i-k}$ 。

code

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=2005;
const int mod=1e9+9;
int n,k;
ll dp[N],ans,f[N],inv[N];
ll fpow(ll a,ll b){
	ll res=1;
	while(b){
		if(b&1)
			res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}
void init(){
	f[0]=inv[0]=1;
	for(int i=1;i<=n;i++)
		f[i]=f[i-1]*i%mod;
	inv[n]=fpow(f[n],mod-2);
	for(int i=n-1;i>=1;i--)
		inv[i]=inv[i+1]*(i+1)%mod;
}
ll C(ll a,ll b){
	return f[a]*inv[b]%mod*inv[a-b]%mod;
}
int main(){
	ll a[N],b[N],c[N];
	scanf("%d%d",&n,&k);
	if((n+k)%2){
		printf("0");
		return 0;
	}
	k=(n+k)/2;
	init();
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	for(int i=1;i<=n;i++)
		scanf("%lld",&b[i]);
	sort(a+1,a+1+n);
	sort(b+1,b+1+n);
	for(int i=1,j=0;i<=n;i++){
		while(b[j+1]<a[i]&&j<n)
			j++;
		c[i]=j;
	}
	dp[0]=1;
	for(int i=1;i<=n;i++)
		for(int j=n;j>=0;j--)
			dp[j]=(dp[j]+dp[j-1]*max(0ll,(c[i]-j+1)))%mod;
	for(int j=1;j<=n;j++)
		dp[j]=dp[j]*f[n-j]%mod;
	for(int i=k;i<=n;i++)
		ans=(ans+fpow(-1,i-k)*C(i,k)*dp[i]%mod+mod)%mod;
	printf("%lld",ans);
}