●BZOJ 3622 已经没有什么好害怕的了

时间：2022-09-21 15:53:35

题链：

http://www.lydsy.com/JudgeOnline/problem.php?id=3622

题解：

容斥，dp
1).可以求出需要多少对"糖果>药片"(K对);
2).把两个数组A,B从小到大排序。
然后求出 nxt[i]表示 A[i]>B[nxt[i]] 且 nxt[i]为能取到的最大值
换句话说，nxt[i]表示有多少个 B的元素小于A[i]
3).定义 dp[i][k]表示前 i个A中有 k个选择了比它小的 B元素，其它的暂时不选 的方案数。
转移显然 dp[i][k]=dp[i-1][k](1)+dp[i-1][k-1]*(nxt[i]-(k-1))(2)
(1)式表示当前这个A元素暂时不选与它匹配的B元素。
(2)式表示当前这个A元素选择一个比它小的B元素与它匹配。
    那么显然会有nxt[i]-(k-1)种选择。（应该懂了排序和求nxt[]的目的了吧）
求出了 dp[N][k]后，但是还有 (N-k)个元素没有匹配怎么办？
直接把 dp[N][k]*(N-k)! 表示剩下的元素随意匹配。
那么这时 dp[N][k]的含义即为：全部匹配后，至少有 k 对 "糖果>药片"的方案数(但是有重复的统计)。
然后为了求出恰好有 K 对 "糖果>药片"的方案数。就需要用到容斥：

4).容斥
不难发现，每个 dp[N][k+1]的方案在 dp[N][k]里出现了 C(k+1,k)次，
那么需要减去重复的。容斥系数如下：
dp[N][k]     :1
dp[N][k+1]     :-C(k+1,k)
dp[N][k+2]    :+C(k+2,k)
...
dp[N][k+j]    :(-1)^(j)*C(k+j,k)
诶，这个容斥系数怎么推出来的呢。看看这个题目的解法，一样的套路哦。

所以把那些东西加起来就是答案了。

另外，还可以更加直接暴力一点：
从后往前枚举 k,计算出 f[k]，表示全部匹配后，恰好有 k 对 "糖果>药片"的方案数。
                    　　N
那么 f[k]=dp[N][k] - (  ∑ f[j]*C(j,k) )  , 即直接把多余的重复减去就好了。
                  　　j=k+1

代码：

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define _ %mod

#define MAXN 2500

#define filein(x) freopen(#x".in","r",stdin);

#define fileout(x) freopen(#x".out","w",stdout);

using namespace std;

const int mod=1000000009;

int dp[MAXN][MAXN],C[MAXN][MAXN],fac[MAXN],A[MAXN],B[MAXN],nxt[MAXN];

int N,K,ANS;

int main()

{

	scanf("%d%d",&N,&K);

	if((N+K)&1) return printf("0"),0;

	else K=(N+K)/2; fac[0]=1;

	for(int i=1;i<=N;i++) fac[i]=(1ll*fac[i-1]*i)_;

	for(int i=0;i<=N;i++){

		C[i][0]=1;

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

			C[i][j]=(1ll*C[i-1][j-1]+C[i-1][j])_;

	}

	for(int i=1;i<=N;i++) scanf("%d",&A[i]);

	for(int i=1;i<=N;i++) scanf("%d",&B[i]);

	sort(A+1,A+N+1); sort(B+1,B+N+1); B[N+1]=0x3f3f3f3f;

	for(int i=1,j=0;i<=N;i++){

		while(B[j+1]<A[i]) j++; nxt[i]=j;

	}

	dp[0][0]=1;

	for(int i=1;i<=N;i++){

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

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

			dp[i][k]=(1ll*dp[i-1][k]+1ll*dp[i-1][k-1]*max(nxt[i]-k+1,0)_)_;

	}

	for(int i=K;i<=N;i++){

		dp[N][i]=(1ll*dp[N][i]*fac[N-i])_;

		ANS=(ANS+1ll*dp[N][i]*C[i][K]*(((i-K)&1)?-1:1)_+mod)_;

	}

	/*for(int i=N;i>=K;i--){

		dp[N][i]=(1ll*dp[N][i]*fac[N-i])_;

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

			dp[N][i]=(1ll*dp[N][i]-1ll*dp[N][j]*C[j][i]_+mod)_;

	}*/

	printf("%d",dp[N][K]);

	return 0;

}

相关文章