[总结] 容斥原理

[总结] 容斥原理

本篇文章用于介绍简单的容斥原理。

定义

• 加上多减的，减去多加的。（可以画 Venn 图来理解）

适用条件

一般套路如下：

• 总方案数容易求得。
• 把 每个集合看成打破 \(|S|\) 条限制的非法方案集合，最后求得的 \(|\bigcup_{i=1}^nS_i|\) 的意义就是 所有非法方案总数。
• 一般可以通过 等价转化 将容斥过程中的方案数计算出来。
• 数据范围较小的数数题（允许状压）。

我们把每一条限制看成集合元素，枚举每一个集合，因为最后是减去不合法方案，所以容斥系数全部由 \((-1)^{|S|-1}\) 变为 \((-1)^{|S|}\)。

其中 \(|S_1 \cup S_2|\) 就等价于打破 \(S_1\) 和 \(S_2\) 至少一个的方案数，\(|S_1 \cap S_2|\) 表示打破 \(S_1\) 和 \(S_2\) 所有限制的方案数。

由于容斥过程中是求 \(∩\)，所以考虑第二种。

换句话说就是 枚举所有条件集合，这就相当于 枚举了所有相交后的集合。

例题

[HAOI2008]硬币购物

给你四种面值 \(c_i\) 的硬币，每种硬币有无限个，求得在限制每种硬币使用个数 \(d_i\) 的前提下凑成 \(s\) 价值的方案数。

先考虑没有限制，跑一遍完全背包即可，可以得到总方案数。

考虑打破限制的情况：

当前集合为 \(S\)，有第 \(i\) 条限制，那么我就强制选 \((d_i+1)\times c_i\) 的第 \(i\) 种硬币即可。

这体现了上面说的：一般可以通过等价转化将容斥过程中的方案数计算出来。

注意：容斥过程中也许并不一定算出总方案数，因为这就是 \(S=0\) 的情况。

对于集合 \(S\) 中的元素，是强制打破，其它条件随意。

比较板的容斥。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template <typename T>
inline T read(){
	T x=0;char ch=getchar();bool fl=false;
	while(!isdigit(ch)){if(ch==‘-‘)fl=true;ch=getchar();}
	while(isdigit(ch)){
		x=(x<<3)+(x<<1)+(ch^48);ch=getchar();
	}
	return fl?-x:x;
}
#define LL long long
const int maxn = 1e5 + 10;
LL f[maxn];
LL val[10],d[10],q,s;
void init(){
	f[0]=1;
	for(int i=1;i<=4;i++)
		for(int j=val[i];j<=100000;j++)f[j]+=f[j-val[i]];
}
#define read() read<LL>()
int main(){
	for(int i=1;i<=4;i++)val[i]=read();q=read();
	init();
	while(q--){
		for(int i=1;i<=4;i++)d[i]=read();
		s=read();
		LL ans=0;
		for(int S=0;S<(1<<4);S++){
			LL sz=0,fl,sum=0;
			for(int i=0;i<4;i++)if((S>>i)&1){
				sz++;sum+=(d[i+1]+1)*val[i+1];
			}
			if(s<sum)continue;
			fl=((sz&1)?(-1):1);
			ans+=fl*f[s-sum];
		}
		printf("%lld\n",ans);
	}
	return 0;
}

CF451E Devu and Flowers

多重集的组合数。（早期代码）

#include <iostream>
#include <cstdio>
#include <set>
#include <cstring>
#include <algorithm>
using namespace std;
#define LL long long
const int P = 1000000007;
const int maxn = 22;
LL m,a[maxn],ans=0;
LL inv[maxn],n;
LL power(LL a,LL b){
	LL res=1;
	while(b){
		if(b&1)res=res*1LL*a%P;
		a=1LL*a*a%P;
		b>>=1;
	}
	return res;
}
LL C(LL n,LL m){
	if(n<0 || m<0 || n<m)return 0;
	n%=P;
	if(n==0 || m==0)return 1LL;
	LL res=1;
	for(int i=0;i<m;i++)res=res*(n-i)%P;
	for(int i=1;i<=m;i++)res=res*inv[i]%P;
	return res;
}
void init(){
	for(int i=1;i<=20;i++)inv[i]=power(i,P-2);
	return ;
}
int main(){
	init();
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)scanf("%lld",a+i);
	for(int s=0;s<(1<<n);s++){
		if(s==0){
			ans=(ans+C(n+m-1,n-1))%P; 
			//cerr<<ans<<endl;
		}
		else{
			LL tmp=n+m;
			int p=0;
			for(int i=1;i<=n;i++){
				if(s&(1<<i-1)){
					p++;
					tmp-=a[i];
				}
			}
			tmp-=p+1; 
			if(p&1){
				ans=(ans-C(tmp,n-1))%P;
			}
			else{
				ans=(ans+C(tmp,n-1))%P;
			}
		}
	}
	printf("%lld",(ans+P)%P);
	return 0;
}

【2018.10雅礼集训day7】Silhouette

从递推的角度理解容斥原理

给定一个 \(n\times n\) 的网格图，每一列和每一行都有最大值是多少的限制，求填数的方案数。

首先可以对行和列分开考虑，划分为每一块最大值都相同的区域，设这个最大值为 \(w\) 。

对行和列分开排序，这样做的好处有两个：

1. 线性找到需要的最大值相同的区域。
2. 其上面和左面的所有区域可以“随便填”。

随便填的意思是：不超过当前最大值的数都可以填，不需要考虑其它影响。

考虑当前的矩形：

设 \(f_i\) 表示 \(a\) 列中有 \(i\) 列是强制不合法的，其它列随意。

那么首先需要满足 \(b\) 行的限制，然后 \(lb\) 上半边、\(i\) 左半边是可以随意选的，\(i\) 右半边因为要强制不合法，所以只能选 \([0,w-1]\) 之间的 \(w\) 个数。

int calc(int a,int b,int la,int lb,int w){
	int res=0;
	for(int i=0;i<=a;i++){
		int tmp=power(power(w+1,la+a-i)-power(w,la+a-i)+P,b);
		tmp=1LL*tmp*power(w+1,1LL*lb*(a-i))%P;
		tmp=1LL*tmp*power(w,1LL*(lb+b)*i)%P;
		int inv=1LL*invfac[i]*invfac[a-i]%P;
		tmp=1LL*tmp*inv;
		if(i&1)res=(res-tmp+P)%P;
		else res=(res+tmp)%P;
	}
	res=1LL*res*fac[a]%P;
	return res;
}

细节部分

• 本题容斥的实现

\(f_i\) 的下标就表明了状态 \(S\) 的 \(size\)，或者说，可以通过组合数、递推等手段实现 \(S\) 的非暴力枚举，实现同一类 \(S\) 的求解。

• "随意“的意义

随意是不能超过当前全集 \(S\) 的。

因此在填数的时候，对于当前的一块矩阵，最多只能填到 \(w\) 的数值。

也就是说，不要混淆了研究对象。

• 选择区域的界限

对当前有影响的、合法的、全集 \(U\) 中的区域才是需要考虑到的。

或者说仅仅关心的是当前矩形填充情况，下面的矩形区域不需要考虑。

[总结] 容斥原理

原文：https://www.cnblogs.com/Liang-sheng/p/15134204.html