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

優點：代碼簡潔、通用、易於處理「至少滿足 k 個條件」等變體。

2. 遞歸 DFS 法

適用於條件間有依賴關係、或需剪枝的場景。

void dfs(int idx, int cnt, long long cur_lcm) {
    if (idx == m) {
        if (cnt == 0) return;
        long long add = total / cur_lcm;
        if (cnt % 2) ans += add; else ans -= add;
        return;
    }
    dfs(idx+1, cnt, cur_lcm);                    // 不選
    dfs(idx+1, cnt+1, lcm(cur_lcm, a[idx]));     // 選
}

經典應用場景

場景 1：求 1~n 中能被任意一個給定數整除的數的個數

給定 a[1..m]，求 |{x ∈ [1,n] : ∃i, x % a[i] == 0}|

long long solve(int n, vector& a) {
    int m = a.size();
    long long ans = 0;
    for (int mask = 1; mask < (1<>i & 1) {
            lcm = lcm / gcd(lcm, a[i]) * a[i];
            if (lcm > n) { overflow = true; break; }
        }
        if (overflow) continue;
        int bits = __builtin_popcount(mask);
        if (bits & 1) ans += n / lcm;
        else ans -= n / lcm;
    }
    return ans;
}

場景 2：排列組合中的「至少/至多」條件

例：n 個球放入 m 個盒，每箱至少 1 個。
總方案 m^n，減去至少一個箱子為空的方案。
設 A_i 為第 i 個箱子為空，則合法方案 = m^n - |∪A_i|，用容斥計算並集。
|A_i| = (m-1)^n，|A_i ∩ A_j| = (m-2)^n...
答案 = Σ(-1)^k * C(m,k) * (m-k)^n

場景 3：網格路徑避開障礙點

從 (0,0) 走到 (n,m)，只能向右/向上，避開 k 個障礙點。
總路徑 = C(n+m, n)。
對每個障礙點子集，計算經過這些點的路徑數（按座標排序後分段相乘），容斥加減。

進階技巧

1. 互質優化

若集合條件互質（如質數），LCM 直接相乘，無溢出風險。

2. 反向容斥

求「滿足所有條件」的個數 = 總數 - 滿足至少一個相反條件的個數。
有時反向條件更少，計算更快。

3. 莫比烏斯反演關聯

容斥原理是莫比烏斯反演在集合論上的體現。對於「整除」類問題，莫比烏斯函數 μ(d) 可直接給出係數，避免枚舉子集。
例：求 [1,n] 中與 m 互質的數 = Σ μ(d) * ⌊n/d⌋，d|m。

4. 最小排除原理 (MEX) 變體

求最小不滿足的條件編號，可二分答案 + 容斥判定。

常見陷阱

1. LCM 溢出：計算 LCM 時檢查 lcm > limit 直接跳過
2. 空集處理：mask = 0 不參與容斥，對應總集合
3. 條件重複：輸入可能含重複數字，需去重
4. 係數符號：奇數集合加、偶數集合減，別搞反
5. 邊界條件：n=0 或集合為空時的處理

經典例題推薦

總結

• 容斥原理核心：**奇加偶減**，將複雜並集轉化為交集計算
• 二進制枚舉最通用，m ≤ 20 時首選
• DFS 適合有依賴/需剪枝場景
• LCM 溢出、符號正確、去重是三大實戰細節
• 進階可結合莫比烏斯反演優化整除類問題

多做幾道模板題，容斥思維就會肌肉記憶化。