前言

这是我在中考结束后写的第一篇博客，关于中考他死了。

接下来还有FFT等一众博客要更新，只能慢慢来了。

部分算法为中考前集训学的，现在需要回忆下才能口胡出来，所以先更这篇昨天学习的容斥及广义容斥的姿势。

本文有部分参考于Parsnip的博文可以去他那里补充看看。

正文

容斥原理

这个大家或多或少都接触过，就是给出一些不同性质包含不同数量元素的集合，然后求含有任意一种性质的元素个数(集合并的大小)，或是求不具有任意一种性质的元素个数（集合并补集大小）。

这些都可以通过容斥来做，用至少含有任意一种性质的集合大小-至少含有任意两种性质的集合大小+至少含有任意三种性质的集合大小……就可以求出含有任意一种性质的元素个数，也就是并集大小了。

通过维恩图我们可以用数形结合的思想来理解，那么我们还可以通过组合数学的方法来理解容斥原理。容斥原理一般在计数问题中常见，我们不难发现，容斥原理的作用就是去重，有些状态会被重复统计，所以要去掉，但是如何知道这些状态重复统计了几遍呢？同样可以通过组合数学求解。比如在求至少含有一个性质的集合大小时，假设你组合数统计到了$a$,那么剩下的数就可以随便选了，假设选到了$b$。那么当统计到$b$时又会把$a$统计一遍，所以对于至少含有$x$种性质的集合大小的统计方案时，含有$y(y>=x)$种性质的集合大小会统计多$C(x,y)$遍。

但是如果从$1$开始的话就有一个很优秀的性质，就是统计多的可以通过后面的消去(可以自己算下，也可以通过维恩图理解)，所以就可以通过一加一减这样的操作实现。

广义容斥原理

所谓广义容斥原理，就是求的不再是不含有任意$1$种性质的元素个数了，而是含有任意$k$种性质的元素个数。可能有些读者会认为用至少含有任意$k$种性质的集合大小-至少含有任意$k+1$种性质的集合大小+至少含有任意$k+2$种性质的集合大小……就可以求出含有任意$k$种性质的元素个数，但这其实是错的，因为容斥原理之所以成立是因为之前在至少含有$[1-k)$性质的集合的内已经消除掉一些$[k,n]$之间的贡献，所以直接加减即可，但是现在并没有。所以要加权，而加的权就是之前说过的$C(x,y)$,放到$k$中也就是$C(k,i)$。这样的话公式即为：至少含有任意$k$种性质的集合大小*$C(k,k)$-至少含有任意$k+1$种性质的集合大小*$C(k,k+1)$+至少含有任意$k+2$种性质的集合大小*$C(k,k+2)$…。

这样就可以通过至少含有$k$种性质，$k+1$种，$k+2$种…来求出正好含有任意$k$种性质的元素个数了。

例题讲解

集合计数

发现要求交集为k的方案数，转换为求交集大小至少为$k,k+1,k+2…n$，固定一个大小的交集，方案数为$C(x,n)$，$x$即为$k,k+1,k+2…n$，然后剩下n-x个位置共有$2^{n-x}$个子集，每个子集可以选或不选（相当于在选出的$x$个位置上加上这个子集就是你选出的其中一个集合），但是不能都不选（相当于你选了这x个位置两边，重复）所以方案数为$C(x,n)*(2^{2^{n-x}}-1)$但是不能保证随机选择的这些集合交集为$0$所以是至少为$x$，可能更多，然后用广义容斥容斥出恰好交集为$k$的方案数即可。（其实题解在n=k的时候都是有解的。。。不知道怎么回事，应该是无解的，因为不能选重集。。。）

#include<bits/stdc++.h>
#define LL long long
#define Mod 1000000007
using namespace std;
LL N,K,answer=0;
inline void read(LL &x)
{
	LL f=1;x=0;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=(x<<3)+(x<<1)+(ch&15);ch=getchar();}
	x*=f;
} 
inline LL f_pow(LL base,LL index,LL mod)
{
	LL res=1;
	while (index)
	{
		if (index&1) res=1*res*base%mod;
		base=1*base*base%mod;
		index>>=1;
	}
	return res%mod;
}
inline LL get_C(LL M,LL N)
{
	LL A=1,B=1;
	for (LL i=1;i<=N;i++) A=A*i%Mod;
	for (LL i=1;i<=M;i++) B=B*i%Mod;
	for (LL i=1;i<=N-M;i++) B=B*i%Mod;
	return A%Mod*f_pow(B,Mod-2,Mod)%Mod;
}
int main()
{
	read(N),read(K);
	LL C1=get_C(K,N)%Mod,C2=1;
	for (LL i=K;i<=N;i++) answer=(answer%Mod+(((i-K)&1)?-1:1)%Mod*C1%Mod*(f_pow(2,f_pow(2,N-i,Mod-1)%Mod,Mod)-1+Mod)%Mod*C2%Mod+Mod)%Mod,C1=C1%Mod*(N-i)%Mod*f_pow(i+1,Mod-2,Mod)%Mod,C2=C2%Mod*(i+1)%Mod*f_pow(i-K+1,Mod-2,Mod)%Mod;//Mod-1是因为欧拉定理。
	cout<<(answer+Mod)%Mod<<endl;
	return 0;
}

已经没有什么好害怕的了

设糖比药大为$a$组，药比糖大为$b$组。

那么$a+b=n$ $a-b=k$ 则 $a=(n+k)/2组$

首先若$n+k$不是偶数则输出$0$

然后对于糖从大到小排个序，对于药从大到小排个序。

对于一颗药二分出比他大的糖果个数。然后设f[i][j]为到第$i$颗药之前配对糖比药大有$j$对的方案数$f[i][j]=f[i-1][j]+f[i-1][j-1]*(比i颗药大的糖果数-(j-1))$在这里从大到小排序糖的意义就出来了，因为之前配对的药也可以配对当前这颗糖，若从小到大排序则不一定，就不可以用比$i$颗药大的糖果数来减$(j-1)$了。

最后$f[n][i]*(n-i)!$就是至少$i$对的方案数，因为剩下$(n-i)$颗糖药随便配也可能出现糖比药大的情况，然后广义容斥就ok了。

#include<bits/stdc++.h>
#define Maxn 2005
#define Mod 1000000009
#define LL long long
using namespace std;
inline void read(LL &x)
{
	LL f=1;x=0;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=(x<<3)+(x<<1)+(ch&15);ch=getchar();}
	x*=f;
}
bool cmp(LL a,LL b){return a>b;}
LL n,k,answer=0,c[Maxn],m[Maxn],Max[Maxn],f[Maxn][Maxn],fac[Maxn];
inline LL get_Max(LL x)
{
	LL L=1,R=n;
	while (L<=R){LL Mid=L+R>>1;if (c[Mid]<x) R=Mid-1;else L=Mid+1;}
	return R;
}
inline LL f_pow(LL base,LL index)
{
	LL res=1;
	while (index)
	{
		if (index&1) res=(res*base)%Mod;
		base=(base*base)%Mod;
		index>>=1;	
	}	
	return res%Mod;
} 
int main()
{
	read(n),read(k);
	if ((n+k)&1) return puts("0"),0;
	k=(n+k)/2;
	for (LL i=1;i<=n;i++) read(c[i]);for (LL i=1;i<=n;i++) read(m[i]);
	sort(m+1,m+n+1,cmp);sort(c+1,c+n+1,cmp);fac[0]=1;
	for (LL i=1;i<=n;i++) Max[i]=get_Max(m[i]),fac[i]=fac[i-1]*i%Mod;
	f[0][0]=1;
	for (LL i=1;i<=n;i++)
	{
		f[i][0]=1;
		for (LL j=1;j<=i;j++) f[i][j]=(f[i-1][j]+f[i-1][j-1]%Mod*(Max[i]-(j-1))%Mod+Mod)%Mod;
	}
	for (LL C=1,i=k;i<=n;i++) 
	{
		LL tmp=f[n][i]*fac[n-i]%Mod;
		answer=(answer+(((i-k)&1)?-1:1)*tmp%Mod*C%Mod+Mod)%Mod;
		C=C%Mod*(i+1)%Mod*f_pow(i-k+1,Mod-2)%Mod;
	}
	cout<<answer<<endl;
	return 0;
}