前言
这是我在中考结束后写的第一篇博客,关于中考他死了。
接下来还有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;
}