組合數學核心：容斥原理原理與實戰技巧全解析

組合數學核心：容斥原理原理與實戰技巧全解析

在組合數學中，容斥原理是求解帶條件組合數的利器。它的核心思想：通過「加加減減」修正重複計數，最終得到滿足條件的元素個數。

基本公式

兩集合： |A ∪ B| = |A| + |B| - |A ∩ B|
三集合： |A ∪ B ∪ C| = |A|+|B|+|C| - |A∩B|-|A∩C|-|B∩C| + |A∩B∩C|

為何最後要加回三重交？因為在減去兩兩交集時，三重交集被減了三次，需加回一次抵消。

黃色區域為目標區域

常用實現方法

1. 二進制枚舉法（子集枚舉）

若集合有 m 個性質/條件，對應 m 位二進制數。0 到 2^m-1 的每個數代表一個子集：第 i 位為 1 表示包含第 i 個性質。遍歷所有子集，根據 1 的個數奇偶性決定加減。優點：代碼簡潔，自動枚舉所有子集。

2. 遞歸/DFS 法

利用深度優先搜索生成子集，邊生成邊計算貢獻。適用於子集元素不固定、或需剪枝的情況。無統一模板，需根據具體題目設計搜索順序與狀態。

容斥原理的通用模式

• 「奇數個性質加，偶數個性質減」—— 這是針對「至少滿足一個性質」的情況。
• 若求「不滿足任何性質」的個數，則用總數減去「至少滿足一個」的個數。

實戰心得

容斥原理概念簡單，實戰卻極其靈活多變。每道題的「性質」定義不同，如何劃分性質、如何計算交集大小、如何處理邊界，都需要具體問題具體分析。關鍵在於：
1. 正確定義「性質」（通常是「不滿足條件」的反面）。
2. 高效計算任意子集對應的交集大小（常涉及數論、組合計數、DP 等）。
3. 注意邊界與取模運算。
多做經典題（如 HDU 4407、求互質數個數、排列組合去重等），積累「性質建模」經驗，方能得心應手。