【离散数学】容斥原理

大家好，欢迎来到IT知识分享网。

容斥定理

简单版本：

对于上述图片，求$|A\cup B\cup C|$
结果为$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|B\cap C|-|C\cap A|+|A\cap B\cap C|$

一般情况

公式：$\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}^m{S}_{a_i}\right|$

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

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

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

大概就是这个意思。

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

例题1 能被整除的数

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

给定一个整数 n和 m 个不同的质数 $p_1,p_2,\dots ,p_m$。
请你求出 1∼n 中能被 $p_1,p_2,\dots ,p_m$中的至少一个数整除的整数有多少个。

思路：

在1-n中能被x整除的个数：$\lfloor \frac{n}{x}\rfloor$
在1-n中能被x,y整除的个数：$\lfloor \frac{n}{xy}\rfloor$
在1-n中能被x,y,z整除的个数：$\lfloor \frac{n}{xyz}\rfloor$
…
然后就可以根据公式求结果，有m个质数，共有m个集合，每次会选中若干个集合，代表几个之间的交集（参照上面容斥定理公式）

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

选中集合个数为偶数，前面符号为负
选中集合个数为奇数，前面符号为正

#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 个盒子中有 $A_i$ 枝花。同一个盒子内的花颜色相同，不同盒子内的花颜色不同。Devu 要从这些盒子中选出 m 枝花组成一束，求共有多少种方案。若两束花每种颜色的花的数量都相同，则认为这两束花是相同的方案。结果需对 $10^9+7$ 取模之后方可输出

思路

• 理想情况

首先去掉限制考虑理想情况，即每个盒子的花的个数有无限个，设第$i$个盒子取出$x_i$朵花

则$x_1+x_2+x_3+\dots +x_n=m,x_i\ge 0$,总方案数为$C_{n+m-1}^{n-1}$种

• 有限制的情况

$x_1,x_2,\dots ,x_n$同时满足限制条件才可，我们考虑从补集去求（总情况数减去相反的情况）

补集情况下：

$x_1+x_2+x_3+\dots +x_n=m,x_1>A_1,x_2>A_2,x_3>A_3\dots \dots x_n>A_n$
第i个限制（$x_i>A_i$）的情况满足个数我们当作一个集合$s_i$

• 总数：$C_{n+m-1}^{n-1}$
• 题目的补集：$|s_1\bigcup s_2\bigcup s_3\dots \dots \bigcup s_n|$
• 结果为：$C_{m+n-1}^{n-1}-|s_1\bigcup s_2\bigcup s_3\dots \dots \bigcup s_n|$

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

$s_1\cap s_2$同理
答案为$C_{m+n-1-(A_1+1)-(A_2+1)}^{n-1}$

最后枚举所有的情况数，使用二进制方法进行枚举，枚举$[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

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

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

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

最后再除以总的情况数 $C_{h\ast w}^k$ 即可

#include<bits/stdc++.h> using namespace std; using ll = long long; const int mod = ; 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; }