首先我们排个序，然后列一个dp方程
设$f[i][j]$为前i小的糖果至少匹配j个药片的数量
那么我们可以利用单调性把这个dp优化到$O(n^2)$
之后我们发现这个可能会重复统计
我们考虑怎么消除重复的部分
首先一个糖果匹配后面药片的总数为$n!$
然后其中重复统计的个数为之后计算的所有dp数组的值乘上一个组合数
那么我们倒着容斥就做完了
详见代码
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=2005;
const long long P=1000000009ll;
int n,m,k;
long long a[N],b[N],C[N][N],fac[N],f[N][N];
int main(){
freopen("3622.in","r",stdin);
freopen("3622.out","w",stdout);
scanf("%d %d",&n,&m);
if((n+m)&1){puts("0");return 0;}
m=n+m>>1;
C[0][0]=fac[0]=f[0][0]=1;
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+n+1);sort(b+1,b+n+1);
for(int i=1;i<=n;i++){
fac[i]=fac[i-1]*i%P;
C[i][0]=C[i][i]=1;
for(int j=1;j<i;j++)C[i][j]=(C[i-1][j]+C[i-1][j-1])%P;
}
for(int i=1;i<=n;i++){
while(k<n && a[i]>b[k+1])k++;f[i][0]=1;
for(int j=0;j<=i;j++)f[i][j]=(f[i-1][j]+f[i-1][j-1]*max(k-j+1,0))%P;
}
for(int i=n;i>=m;i--){
f[n][i]=f[n][i]*fac[n-i]%P;
for(int j=i+1;j<=n;j++){
f[n][i]-=f[n][j]*C[j][i];
f[n][i]=(f[n][i]+P)%P;
}
}
printf("%lld\n",f[n][m]);
return 0;
}
评论 (0)
