8
1
2016
0

[BZOJ3622] 已经没有什么好害怕的了

首先我们排个序,然后列一个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;
}
Category: BZOJ | Tags: OI bzoj | Read Count: 808

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com