容斥定理

# 容斥定理

基本描述

简单版本

对于上述图片,求ABC|A\cup B \cup C|

结果为ABC=A+B+CABBCCA+ABC|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|B\cap C|-|C\cap A|+|A\cap B\cap C|

一般描述

公式:

i=1nSi=m=1n(1)m1ai<ai+1i=1mSai\left|\bigcup_{i=1}^{n}S_i\right|=\sum_{m=1}^n(-1)^{m-1}\sum_{a_i<a_{i+1} }\left|\bigcap_{i=1}^mS_{a_i}\right|

大家应该是看不懂吧,反正我是看不懂

我理解的通俗的意思就是:

n个集合的并集等于n个集合选择一个的情况中所有情况的交-n个集合中选择两个所有情况中两两的交+n个集合中选择三个中所有情况三个的交-选择四种的交+选择五种的交-…

稍微用公式表示一下:

A1...An=A1+A2+...+An(A1A2+...+AiAj)+(A1A2A3+...+AiAjAk)(四个之间的交)+(五个之间的交)......|A_1\cup...\cup A_n| = \\ |A_1|+|A_2|+...+|A_n|\\ -(|A_1 \cap A_2|+...+|A_i \cap A_j|)\\ +(|A_1 \cap A_2 \cap A_3|+...+|A_i \cap A_j \cap A_k|)\\ -(\text{四个之间的交})\\ +(\text{五个之间的交})\\ ......

大概就是这个意思。

  • 选择的个数为偶数次,前面符号为负
  • 选择的个数为奇数次,前面符号为正

参考链接:
https://oi-wiki.org/math/combinatorics/inclusion-exclusion-principle/

例题1 能被整除的数

题目链接:https://www.acwing.com/problem/content/892/

给定一个整数 nm 个不同的质数 p1,p2,,pmp_1,p_2,…,p_m
请你求出 1∼n 中能被 p1,p2,,pmp_1,p_2,…,p_m中的至少一个数整除的整数有多少个。


思路:

先简单的举个例子:
质数有2,3,5,7,11五个
能被2整除的有2,4,6,8 …
能被3整除的有3,6,9,12…

问的是被至少一个整除就行,那么上述例子中6是重复的
也就是我们可以把能被一个质数整除的个数当作一个集合,这么多质数组成的集合有重合的,我们要求的是这么多集合的并集,满足容斥定理

1-n中能被x整除的个数:nx\lfloor \frac{n}{x}\rfloor
1-n中能被x,y整除的个数:nxy\lfloor \frac{n}{xy}\rfloor
1-n中能被x,y,z整除的个数:nxyz\lfloor \frac{n}{xyz}\rfloor

然后就可以根据公式求结果,有m个质数,共有m个集合,每次会选中若干个集合,代表几个之间的交集(参照上面容斥定理公式)

几个集合之间的交集:就是一个数能同时被这选中的几个质数整除

选中集合个数为偶数,前面符号为
选中集合个数为奇数,前面符号为

枚举所有的集合:
我们采用二进制的方法,枚举[1,2m1][1,2^{m}-1],统计其中1的个数即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 20;
int p[N];
int n,m;

int main()
{
	cin>>n>>m;
	for(int i=0;i<m;i++) cin>>p[i];
	
	ll res = 0;
	for(int i=1;i< 1<<m ;i++)
	{
		int cnt = 0;
		ll t = 1;
		for(int j=0;j<m;j++)
		{
			if( i>>j & 1)
			{
				cnt ++ ;//统计选中的个数
				if(t * p[j] > n)//不满足条件,因为大于n了
				{
					t = -1;
					break;
				}
				t *= p[j];
			}
		}
		if(t!=-1)
		{
			if(cnt%2) res += n/t;
			else res -= n/t; 
		}
	}
	cout << res << endl;
	return 0;
}

例题2

题目链接:https://www.acwing.com/problem/content/216/

Devu 有 N 个盒子,第 i 个盒子中有 AiA_i 枝花。同一个盒子内的花颜色相同,不同盒子内的花颜色不同。Devu 要从这些盒子中选出 m 枝花组成一束,求共有多少种方案。若两束花每种颜色的花的数量都相同,则认为这两束花是相同的方案。结果需对 109+710^9+7 取模之后方可输出


思路

  • 理想情况

首先去掉限制考虑理想情况,即每个盒子的花的个数有无限个,设第ii个盒子取出xix_i朵花

x1+x2+x3+...+xn=m,xi0x_1+x_2+x_3+...+x_n= m,x_i \geq 0,总方案数为Cn+m1n1C_{n+m-1}^{n-1}

可以参考链接查看如何计算 :
https://oi-wiki.org/math/combinatorics/inclusion-exclusion-principle/


  • 有限制的情况

限制条件下:
x1+x2+x3+...+xn=m,x1<=A1,x2<=A2,x3<=A3xn<=Anx_1+x_2+x_3+...+x_n= m,x_1<=A_1,x_2<=A_2,x_3<=A_3……x_n<=A_n

x1,x2,...,xnx_1,x_2,...,x_n同时满足限制条件才可,我们考虑从补集去求(总情况数减去相反的情况)

补集情况下:

x1+x2+x3+...+xn=m,x1>A1,x2>A2,x3>A3xn>Anx_1+x_2+x_3+...+x_n= m,x_1>A_1,x_2>A_2,x_3>A_3……x_n>A_n
i个限制(xi>Aix_i>A_i)的情况满足个数我们当作一个集合sis_i

  • 总数:Cn+m1n1C_{n+m-1}^{n-1}
  • 题目的补集:s1s2s3sn|s_1\bigcup s_2\bigcup s_3……\bigcup s_n|
  • 结果为:Cm+n1n1s1s2s3snC_{m+n-1}^{n-1}-|s_1\bigcup s_2\bigcup s_3……\bigcup s_n|

考虑求满足s1s_1的情况数
即第一个必须取至少Ai+1A_i+1支花,那么接下来就化为从n组里面选花,x1>=A1+1,x2>=0,x3>=0,...,xn>=0x_1>=A_1+1,x_2>=0,x_3>=0,...,x_n>=0的情况,可以直接取出Ai+1A_i+1支花放在第一组,那么总数就变成m(A1+1)m-(A_1+1)支花,就化为理想情况(见上文)下的问题了,总数为Cm+n1(A1+1)n1C_{m+n-1-(A_1+1)}^{n-1}

s1s2s_1\cap s_2同理
答案为Cm+n1(A1+1)(A2+1)n1C_{m+n-1-(A_1+1)-(A_2+1)}^{n-1}

最后枚举所有的情况数,使用二进制方法进行枚举,枚举[0,2n1][0,2^n-1],统计二进制位1的个数

奇数个1符号为负
偶数个1符号位正

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 20,mod = 1e9+7;

ll a[N];
ll d = 1;

ll fast(ll a,ll b)
{
	ll res = 1;
	while(b)
	{
		if(b&1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}

ll C(ll x,ll y)
{
	if(x < y) return 0;
	ll u = 1;
	for(ll i = x;i>x-y;i--) u = i % mod * u % mod;
	return u * d % mod;
}

int main()
{
	ll n,m;
	cin >> n >> m;
	for ( int i=0;i<n;i++) cin>>a[i];
	
	for(ll i=1;i<=n-1;i++) d = d * i % mod;
	d = fast(d,mod-2);
	
	ll res = 0 ;
	for(int i=0; i< 1<<n;i++)
	{
		//组合数的下角标   上角标
		ll down = n + m -1,up = n-1;
		int sign = 1;//标记的符号位
		for(int j=0;j<n;j++)
		{
			if(i>>j&1)
			{
				down -= a[j]+1;//下角标减去对应的个数
				sign *= -1;
			}
		}
		res = (res + C(down,up) * sign)%mod; //计算组合数,统计答案
	}
	cout<<(res + mod) % mod<<endl; 
	return 0;
}

例题3 ABC 297 F Minimum Bounding Box 2

AtCoder Beginner Contest 297 F Minimum Bounding Box 2

方法描述

枚举矩形的长h和宽w,长h宽w的矩形的情况数总共有 (Hh+1)×(Ww+1)(H - h + 1) \times (W - w + 1) 个,每个矩形框对应的分数为 h×wh \times w

容斥时,共有四个变量,对应4个二进制位, 对应上下左右四个方向是否收缩1个单位,收缩的总数为奇数时,符号为负,为偶数时,符号为正。

注意容斥变量s是从0开始,0刚好对应总的情况数,所以不用额外计算总的情况数

最后再除以总的情况数 ChwkC_{h * w} ^ k 即可

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int mod = 998244353;
const int N = 1e6;

ll ksm(ll a, ll b) {
	ll res = 1;
	a %= mod;
	while(b) {
		if(b & 1) res = res * a % mod;
		b >>= 1;
		a = a * a % mod;
	}
	return res;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int h, w, k;
	cin >> h >> w >> k;

	vector<ll> fac(N + 1), inv(N + 1);
	fac[0] = 1;
	for(int i = 1; i <= N; i++) {
		fac[i] = fac[i - 1] * i % mod;
	}
	inv[N] = ksm(fac[N], mod - 2);
	inv[0] = 1;
	for(int i = N - 1; i >= 1; i--) {
		inv[i] = inv[i + 1] * (i + 1) % mod;
	}

	auto C = [&](ll n, ll m) -> ll {
		if(n < m || m < 0) return 0;
		return fac[n] * inv[m] % mod * inv[n - m] % mod;
	};

	ll ans = 0;
	for(int i = 1; i <= h; i++) {
		for(int j = 1; j <= w; j++) {
			ll res = 0;
			for(int s = 0; s < 16; s++) {
				int u = __builtin_popcount(s & 3);
				int v = __builtin_popcount(s & 12);
				res += ((u + v) & 1 ? -1 : 1) * C(max(0, i - u) * max(0, j - v), k) % mod;
				res %= mod;
			}
			ans += res * (h - i + 1) % mod * (w - j + 1) % mod * i % mod * j % mod;
			ans %= mod;
		}
	}
	ans *= ksm(C(h * w, k), mod - 2);
	ans %= mod;
	cout << (ans + mod) % mod << "\n";
	return 0;
}

   转载规则


《容斥定理》 行码棋 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
阶乘逆元和线性逆元 阶乘逆元和线性逆元
逆元简介 a×b≡1(mod  p)a \times b \equiv 1 ( mod\,\,p)a×b≡1(modp),可以称a是b在模p情况下的逆元. 逆元其实就是可以看作倒数 阶乘逆元 方式一: 通过费马小定理求逆元: 当p为素
2022-06-25 2024-10-01
下一篇 
C++ STL超全总结 C++ STL超全总结
C++ STL常用内容总结 我是以打算法竞赛的角度整理的STL知识点,强调使用方法,并不强调原理。 下面会介绍很多C++ STL库里面的模板,在编程中STL犹如神器,实用简洁好用。 STL绝对让你受益无穷! 👉1.vector动态数组
2022-06-22 2024-02-20
  目录