【離散數學】容斥原理
- 部落格主頁: https://blog.csdn.net/qq_50285142
- 歡迎點贊👍收藏✨關注❤留言 📝 如有錯誤，敬請指正
- 🎈點選領取大量學習資源🎈
容斥定理
簡單版本：
對於上述圖片，求
∣
A
∪
B
∪
C
∣
|A\cup B \cup C|
∣A∪B∪C∣
結果為
∣
A
∪
B
∪
C
∣
=
∣
A
∣
+
∣
B
∣
+
∣
C
∣
−
∣
A
∩
B
∣
−
∣
B
∩
C
∣
−
∣
C
∩
A
∣
+
∣
A
∩
B
∩
C
∣
|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|B\cap C|-|C\cap A|+|A\cap B\cap C|
∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣B∩C∣−∣C∩A∣+∣A∩B∩C∣
一般情況
公式： ∣ ⋃ i = 1 n S i ∣ = ∑ m = 1 n ( − 1 ) m − 1 ∑ a i < a i + 1 ∣ ⋂ i = 1 m S a i ∣ \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| ∣⋃i=1nSi∣=∑m=1n(−1)m−1∑ai<ai+1∣⋂i=1mSai∣
大家應該是看不懂吧，反正我是看不懂
我理解的通俗的意思就是：
n個集合的並集等於n個集合選擇一個的情況中所有情況的交-n個集合中選擇兩個所有情況中兩兩的交+n個集合中選擇三個中所有情況三個的交-選擇四種的交+選擇五種的交-…
稍微用公式表示一下：
∣
A
1
∪
.
.
.
∪
A
n
∣
=
∣
A
1
∣
+
∣
A
2
∣
+
.
.
.
+
∣
A
n
∣
−
(
∣
A
1
∩
A
2
∣
+
.
.
.
+
∣
A
i
∩
A
j
∣
)
+
(
∣
A
1
∩
A
2
∩
A
3
∣
+
.
.
.
+
∣
A
i
∩
A
j
∩
A
k
∣
)
−
(
四
個
之
間
的
交
)
+
(
五
個
之
間
的
交
)
.
.
.
.
.
.
|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|)\\ -(四個之間的交)\\ +(五個之間的交)\\ ......
∣A1∪...∪An∣=∣A1∣+∣A2∣+...+∣An∣−(∣A1∩A2∣+...+∣Ai∩Aj∣)+(∣A1∩A2∩A3∣+...+∣Ai∩Aj∩Ak∣)−(四個之間的交)+(五個之間的交)......
大概就是這個意思。
- 選擇的個數為偶數次，前面符號為負
- 選擇的個數為奇數次，前面符號為正
參考連結：
https://oi-wiki.org/math/combinatorics/inclusion-exclusion-principle/
例題1 能被整除的數
題目連結：https://www.acwing.com/problem/content/892/
給定一個整數
n和m個不同的質數 p 1 , p 2 , … , p m p_1,p_2,…,p_m p1,p2,…,pm。
請你求出 1∼n 中能被 p 1 , p 2 , … , p m p_1,p_2,…,p_m p1,p2,…,pm中的至少一個數整除的整數有多少個。
思路：
先簡單的舉個例子：
質數有2，3，5，7，11五個
能被2整除的有2，4，6，8 …
能被3整除的有3，6，9，12…
…
問的是被至少一個整除就行，那麼上述例子中6是重複的
也就是我們可以把能被一個質數整除的個數當作一個集合，這麼多質陣列成的集合有重合的，我們要求的是這麼多集合的並集，滿足容斥定理
在1-n中能被x整除的個數：
⌊
n
x
⌋
\lfloor \frac{n}{x}\rfloor
⌊xn⌋
在1-n中能被x,y整除的個數：
⌊
n
x
y
⌋
\lfloor \frac{n}{xy}\rfloor
⌊xyn⌋
在1-n中能被x,y,z整除的個數：
⌊
n
x
y
z
⌋
\lfloor \frac{n}{xyz}\rfloor
⌊xyzn⌋
…
然後就可以根據公式求結果，有m個質數，共有m個集合，每次會選中若干個集合，代表幾個之間的交集（參照上面容斥定理公式）
幾個集合之間的交集：就是一個數能同時被這選中的幾個質數整除
選中集合個數為偶數，前面符號為負
選中集合個數為奇數，前面符號為正
列舉所有的集合：
我們採用二進位制的方法，列舉 [ 1 , 2 m − 1 ] [1,2^{m}-1] [1,2m−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個盒子中有 A i A_i Ai 枝花。同一個盒子內的花顏色相同，不同盒子內的花顏色不同。Devu 要從這些盒子中選出m枝花組成一束，求共有多少種方案。若兩束花每種顏色的花的數量都相同，則認為這兩束花是相同的方案。結果需對 1 0 9 + 7 10^9+7 109+7 取模之後方可輸出
思路
- 理想情況
首先去掉限制考慮理想情況，即每個盒子的花的個數有無限個，設第 i i i個盒子取出 x i x_i xi朵花
則 x 1 + x 2 + x 3 + . . . + x n = m , x i ≥ 0 x_1+x_2+x_3+...+x_n= m,x_i \geq 0 x1+x2+x3+...+xn=m,xi≥0,總方案數為 C n + m − 1 n − 1 C_{n+m-1}^{n-1} Cn+m−1n−1種
可以參考連結檢視如何計算 :
https://oi-wiki.org/math/combinatorics/inclusion-exclusion-principle/
- 有限制的情況
限制條件下：
x
1
+
x
2
+
x
3
+
.
.
.
+
x
n
=
m
,
x
1
<
=
A
1
,
x
2
<
=
A
2
,
x
3
<
=
A
3
…
…
x
n
<
=
A
n
x_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+x3+...+xn=m,x1<=A1,x2<=A2,x3<=A3……xn<=An
x 1 , x 2 , . . . , x n x_1,x_2,...,x_n x1,x2,...,xn同時滿足限制條件才可，我們考慮從補集去求（總情況數減去相反的情況）
補集情況下：
x
1
+
x
2
+
x
3
+
.
.
.
+
x
n
=
m
,
x
1
>
A
1
,
x
2
>
A
2
,
x
3
>
A
3
…
…
x
n
>
A
n
x_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+x3+...+xn=m,x1>A1,x2>A2,x3>A3……xn>An
第i個限制（
x
i
>
A
i
x_i>A_i
xi>Ai）的情況滿足個數我們當作一個集合
s
i
s_i
si
- 總數： C n + m − 1 n − 1 C_{n+m-1}^{n-1} Cn+m−1n−1
- 題目的補集： ∣ s 1 ⋃ s 2 ⋃ s 3 … … ⋃ s n ∣ |s_1\bigcup s_2\bigcup s_3……\bigcup s_n| ∣s1⋃s2⋃s3……⋃sn∣
- 結果為： C m + n − 1 n − 1 − ∣ s 1 ⋃ s 2 ⋃ s 3 … … ⋃ s n ∣ C_{m+n-1}^{n-1}-|s_1\bigcup s_2\bigcup s_3……\bigcup s_n| Cm+n−1n−1−∣s1⋃s2⋃s3……⋃sn∣
考慮求滿足
s
1
s_1
s1的情況數
即第一個必須取至少
A
i
+
1
A_i+1
Ai+1支花，那麼接下來就化為從n組裡面選花，
x
1
>
=
A
1
+
1
,
x
2
>
=
0
,
x
3
>
=
0
,
.
.
.
,
x
n
>
=
0
x_1>=A_1+1,x_2>=0,x_3>=0,...,x_n>=0
x1>=A1+1,x2>=0,x3>=0,...,xn>=0的情況，可以直接取出
A
i
+
1
A_i+1
Ai+1支花放在第一組，那麼總數就變成
m
−
(
A
1
+
1
)
m-(A_1+1)
m−(A1+1)支花，就化為理想情況(見上文)下的問題了，總數為
C
m
+
n
−
1
−
(
A
1
+
1
)
n
−
1
C_{m+n-1-(A_1+1)}^{n-1}
Cm+n−1−(A1+1)n−1
s
1
∩
s
2
s_1\cap s_2
s1∩s2同理
答案為
C
m
+
n
−
1
−
(
A
1
+
1
)
−
(
A
2
+
1
)
n
−
1
C_{m+n-1-(A_1+1)-(A_2+1)}^{n-1}
Cm+n−1−(A1+1)−(A2+1)n−1
最後列舉所有的情況數，使用二進位制方法進行列舉，列舉
[
0
,
2
n
−
1
]
[0,2^n-1]
[0,2n−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;
}
往期優質文章推薦
領取大量學習資源
涵蓋python基礎 + 進階 + 精通所有課程
還有許多C++等眾多資料等待你的開發
資源始終不是最重要的一環，關鍵是如何找資源才是最重要的，之後我會整理出怎樣找資源，從哪裡找資源，如何高效找資源的文章發於公眾號上，感謝大家支援！