【BZOJ3622】已经没有什么好害怕的了（动态规划，容斥）

题面

题解

很明显的，这类问题是要从至少变成恰好的过程，直接容斥即可。

首先我们要求的是(糖果>药片)=(药片>糖果)+k，再加上保证不存在相同的数，

所以(糖果>药片)+(药片>糖果)=n，解出(糖果>药片)=\(\frac{n+k}{2}\)。

此时我们要求的至少就是“至少存在\(i\)对(糖果>药片)的方案数”。

直接算很麻烦，那就\(dp\)算。首先进行排序。

设\(f[i][j]\)表示前\(i\)对中，(糖果>药片)至少为\(j\)的方案数。

那么，转移显然是\(f[i][j]=f[i-1][j]+f[i-1][j-1]*(s-j+1)\)。

至于后面为啥是\(s-j+1\)不就是\(RabbitNumbering\)那题吗。。。

\(k\)是满足糖果\(i\)>药片\(s\)，\(s\)的最大值，显然可以\(O(n)\)预处理。

接下来的容斥就比较简单了吧。。。。

至少\(i,i>k\)次会被至少\(k\)次重复计算\(C_i^k\)次，容斥减掉就好了。。。

计算的时候别忘了除了至少匹配的\(j\)对，剩下的\(n-j\)是可以随意匹配的，这个是要乘阶乘的。。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

#define ll long long

#define MOD 1000000009

#define MAX 2222

void add(int &x,int y){x+=y;if(x>=MOD)x-=MOD;}

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

int a[MAX],b[MAX],f[MAX][MAX];

int jc[MAX],jv[MAX],inv[MAX];

int n,K;

int C(int n,int m){return 1ll*jc[n]*jv[m]%MOD*jv[n-m]%MOD;}

int main()

{

	n=read();K=read();

	if((n+K)&1){puts("0");return 0;}

	jc[0]=jv[0]=inv[0]=inv[1]=1;

	for(int i=1;i<=n;++i)jc[i]=1ll*jc[i-1]*i%MOD;

	for(int i=2;i<=n;++i)inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;

	for(int i=1;i<=n;++i)jv[i]=1ll*jv[i-1]*inv[i]%MOD;

	for(int i=1;i<=n;++i)a[i]=read();

	for(int i=1;i<=n;++i)b[i]=read();

	sort(&a[1],&a[n+1]);sort(&b[1],&b[n+1]);

	f[0][0]=1;

	for(int i=1,k=0;i<=n;++i)

	{

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

		for(int j=1;j<=i;++j)

		{

			add(f[i][j],f[i-1][j]);

			add(f[i][j],1ll*f[i-1][j-1]*max(k-j+1,0)%MOD);

		}

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

	}

	int d=1,ans=0;K=(n+K)>>1;

	for(int i=K;i<=n;++i,d=MOD-d)add(ans,1ll*f[n][i]*d%MOD*C(i,K)%MOD*jc[n-i]%MOD);

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

	return 0;

}

巴特西

【BZOJ3622】已经没有什么好害怕的了（动态规划，容斥）

【BZOJ3622】已经没有什么好害怕的了（动态规划，容斥）

题面

题解

最新文章

热门文章