CC++ & Algorithm

容斥原理

困难2
语言版本：C++
概述：用生活例子和C++代码教会你如何用容斥原理数数不重复。

容斥原理：加多了要减回来，减多了再加回去 —— 用C++精确数数

1. 什么是容斥原理？—— 数数不重复的秘诀

容斥原理（Inclusion–Exclusion Principle）是一种「算总数时不重不漏」的方法。它的核心是：先全部加起来，再减去多算的部分，如果减多了再加回来…… 这样反复调整，直到每个元素只被算一次。

生活小例子：班级里的兴趣班

  • 只有两样：数学兴趣班有5人，语文兴趣班有4人，但是小美两个班都报了，如果直接5+4=9，小美被数了两次，多算了1次。正确的算法是：5 + 4 - 1 = 8人。这里减去的“1”就是两样都报的人数（交集大小）。
  • 三样兴趣班：数学8人，语文7人，英语6人；同时报数学和语文的3人，数学和英语2人，语文和英语2人；三样都报的1人。总人数 = 8+7+6 - (3+2+2) + 1 = 15人。为什么最后还要加回1？因为两两交集被减掉了，但三样都报的人被减了三次（在每一个两两交集中都被减了一次），实际上应该只减零次（要算一次），所以需要加回来。

口诀：加一次（单集合），减两次（两两交集），加三次（三个交集），减四次…… 也就是奇加偶减：被奇数个集合包含就加，被偶数个集合包含就减。

2. 从零花钱到游戏抽卡——更多生活实例

  • 零花钱统计：小明有5元零花钱，小红有3元，但是两人合起来买了一本8元的书，其中小明出了5元，小红出了3元，那么他们一共花了5+3=8元，这里没有重叠，直接加。但如果两人都从各自的零花钱里拿出2元一起买礼物，那么总花费 = 5+3 - 2 = 6元（因为重叠的2元被重复算了）。
  • 游戏抽卡：在一个卡池里，抽到A角色的概率是20%，抽到B角色的概率是15%，能同时抽到A和B的概率是5%。那么抽到A或B的概率 = 20%+15%-5% = 30%。这其实就是容斥原理在概率中的应用。
  • 排队问题：操场上有同学在踢足球和打篮球。踢足球的有10人，打篮球的有8人，两项都参加的有3人。那么总共参加活动的人数 = 10+8-3 = 15人。如果还有跑步的12人，并且有交叉，就需要用三个集合的公式。

3. C++实战：从两个集合到任意多个集合

第一步：两个集合的并集（保留原有代码并解释）

#include <iostream>
using namespace std;

int main() {
    // 集合 A
    int n; // A 的大小
    cout << "输入集合A的元素个数：";
    cin >> n;
    int a[100];
    cout << "输入" << n << "个数字：";
    for (int i = 0; i < n; i++) cin >> a[i];

    // 集合 B
    int m; // B 的大小
    cout << "输入集合B的元素个数：";
    cin >> m;
    int b[100];
    cout << "输入" << m << "个数字：";
    for (int i = 0; i < m; i++) cin >> b[i];

    // 计算交集大小
    int intersect = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i] == b[j]) {
                intersect++;
                break; // 同一个元素只算一次
            }
        }
    }

    int unionSize = n + m - intersect;
    cout << "并集大小为：" << unionSize << endl;

    return 0;
}

运行示例
A = {1,2,3}, B = {2,4}，交集 {2} 大小=1，并集大小=3+2-1=4。

第二步：三个集合的并集（用数组和循环）

假定有三个集合，分别有 n1, n2, n3 个元素，我们需要统计所有元素的并集大小。可以用三层循环找三个集合都出现的元素（三重交集），以及两两交集。但更通用的方法是位运算枚举所有子集，适合任意多个集合。下面给出一个三个集合的简单实现：

#include <iostream>
using namespace std;

int main() {
    // 集合 A
    int n1; // A 的大小
    cout << "输入第一个集合的元素个数：";
    cin >> n1;
    int a[100];
    cout << "输入" << n1 << "个数字：";
    for (int i = 0; i < n1; i++) cin >> a[i];

    // 集合 B
    int n2; // B 的大小
    cout << "输入第二个集合的元素个数：";
    cin >> n2;
    int b[100];
    cout << "输入" << n2 << "个数字：";
    for (int i = 0; i < n2; i++) cin >> b[i];

    // 集合 C
    int n3; // C 的大小
    cout << "输入第三个集合的元素个数：";
    cin >> n3;
    int c[100];
    cout << "输入" << n3 << "个数字：";
    for (int i = 0; i < n3; i++) cin >> c[i];

    // 计算两两交集大小
    int ab = 0, ac = 0, bc = 0;
    for (int i = 0; i < n1; i++) {
        for (int j = 0; j < n2; j++) {
            if (a[i] == b[j]) {
                ab++;
                break;
            }
        }
    }
    for (int i = 0; i < n1; i++) {
        for (int j = 0; j < n3; j++) {
            if (a[i] == c[j]) {
                ac++;
                break;
            }
        }
    }
    for (int i = 0; i < n2; i++) {
        for (int j = 0; j < n3; j++) {
            if (b[i] == c[j]) {
                bc++;
                break;
            }
        }
    }

    // 计算三重重合大小（三个集合都出现的元素）
    int abc = 0;
    for (int i = 0; i < n1; i++) {
        for (int j = 0; j < n2; j++) {
            if (a[i] == b[j]) {
                for (int k = 0; k < n3; k++) {
                    if (a[i] == c[k]) {
                        abc++;
                        break;
                    }
                }
                break;
            }
        }
    }

    // 容斥原理公式：并集 = A+B+C - (AB+AC+BC) + ABC
    int unionSize = n1 + n2 + n3 - (ab + ac + bc) + abc;
    cout << "三个集合的并集大小为：" << unionSize << endl;

    return 0;
}

运行示例
A = {1,2,3}, B = {2,3,4}, C = {3,4,5}
两两交集：AB={2,3}大小2，AC={3}大小1，BC={3,4}大小2
三重交集：{3}大小1
并集 = 3+3+3 - (2+1+2) + 1 = 9-5+1=5，实际为 {1,2,3,4,5} 共5个，正确。

第三步：通用方法（位枚举，适合CSP-S）

当集合数量很少（比如不超过20个）时，可以用位运算枚举所有子集，然后用容斥原理一次性算出并集大小。这个方法在后面“完整示例”中给出。

4. 常见错误（新手容易掉进的坑）

  • 忘记break导致重复计数：在找交集时，如果集合里重复元素很多（比如{1,1,2}），不break的话，同一个数字会被多次计数。上面的代码用了break，只记录一次。但更严谨的做法是先将集合去重，或者用标记数组。
  • 减多又加错符号：比如三个集合，直接套用两集合公式，减了两两交集后忘记加回三重交集，导致结果偏小。
  • 对元素值重复没处理：如果集合中有重复元素（比如多个1），那么集合本身的大小就应该把重复的只算一次。通常我们处理的是数学集合，不允许重复。所以最好在输入时就确保元素不重复，或者先排序去重。
  • 整数溢出：当数据很大时（比如10^9个元素），虽然题目不会这么出，但注意int可能溢出。不过对于CSP-S，一般用long long。
  • 逻辑失误：容斥原理中“奇加偶减”是针对每个元素是否被计算的次数。理解这个规则需要画韦恩图。

5. 完整示例：用位运算实现任意多个集合的并集

下面是一个更通用的程序，可以输入最多10个集合，利用二进制枚举所有非空子集，根据子集中集合个数的奇偶性来加或减该子集对应的交集大小，最终得到并集大小。这是CSP-S中常用的技巧。

#include <iostream>
using namespace std;

int main() {
    const int MAX_SET = 10; // 最多10个集合
    int k; // 集合个数
    cout << "请输入集合个数（不超过10）：";
    cin >> k;

    int size[MAX_SET]; // 每个集合的大小
    int elements[MAX_SET][100]; // 每个集合的元素，假设最大100个

    for (int i = 0; i < k; i++) {
        cout << "输入第" << i+1 << "个集合的元素个数：";
        cin >> size[i];
        cout << "输入" << size[i] << "个数字：";
        for (int j = 0; j < size[i]; j++) {
            cin >> elements[i][j];
        }
    }

    // 枚举所有非空子集（二进制表示，1表示选中该集合）
    long long total = 0; // 并集大小
    for (int mask = 1; mask < (1 << k); mask++) {
        // 统计当前子集中有多少个集合
        int cnt = 0; // 选中集合的个数
        // 保存当前子集所有集合的交集元素（临时去重标记）
        // 由于最多100个，可以用标记数组，但这里简化：直接求所有集合同时出现的元素
        // 方法：取第一个集合的每个元素，检查是否在所有其他选中的集合中
        // 先找到第一个选中的集合
        int first = -1; // 第一个被选中的集合索引
        for (int i = 0; i < k; i++) {
            if (mask & (1 << i)) {
                if (first == -1) first = i;
                cnt++;
            }
        }
        // 求交集大小：遍历第一个集合的元素
        int intersectSize = 0;
        for (int idx = 0; idx < size[first]; idx++) {
            int val = elements[first][idx];
            bool inAll = true; // 是否在所有选中的集合中
            // 检查其他选中的集合
            for (int i = 0; i < k; i++) {
                if (i == first) continue;
                if (mask & (1 << i)) {
                    // 检查 val 是否在集合 i 中
                    bool found = false;
                    for (int j = 0; j < size[i]; j++) {
                        if (elements[i][j] == val) {
                            found = true;
                            break;
                        }
                    }
                    if (!found) {
                        inAll = false;
                        break;
                    }
                }
            }
            if (inAll) {
                intersectSize++;
            }
        }
        // 容斥：奇数个集合加，偶数个集合减
        if (cnt % 2 == 1) {
            total += intersectSize;
        } else {
            total -= intersectSize;
        }
    }

    cout << "所有集合的并集大小为：" << total << endl;

    return 0;
}

运行示例（三个集合同上）
输入集合个数3，然后依次输入各集合。输出应为5。

6. 延伸学习：容斥原理还能用在哪里？

  • 欧拉函数：求1~N中与N互质的数的个数，可用容斥原理减去N的每个质因数的倍数，加上两两倍数…… 这就是经典的欧拉函数计算。
  • 数论中的倍数问题：求1~N中能被a或b整除的数的个数，直接套用两集合容斥。
  • 概率计算：求多个事件至少发生一个的概率，公式完全一样。
  • 排列组合：错位排列、有限制条件的计数问题。
  • 约瑟夫问题的某些变种也可能用到容斥。

建议你接下来学习位运算枚举、欧拉函数和中国剩余定理，它们经常与容斥原理结合出现。

总结：容斥原理就是“先全部加起来，再减多算的，加回减多的”，记住奇加偶减。用C++实现时，关键是算清楚每个子集的交集大小。现在你可以用这个工具解决很多复杂的计数问题啦！

例题精讲

1单选题

用容斥原理计算三个集合A、B、C的并集元素个数，下列公式正确的是？

A|A∪B∪C| = |A|+|B|+|C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C|
B|A∪B∪C| = |A|+|B|+|C| - |A∩B| - |A∩C| - |B∩C| - 2|A∩B∩C|
C|A∪B∪C| = |A|+|B|+|C| + |A∩B| + |A∩C| + |B∩C| - |A∩B∩C|
D|A∪B∪C| = |A|+|B|+|C| - |A∩B| - |A∩C| - |B∩C| + 2|A∩B∩C|
2判断题

在使用容斥原理求解“至少满足一个条件”的问题时，需要从所有单个条件的元素总数中减去所有两个条件同时满足的元素总数，再加上所有三个条件同时满足的元素总数，以此类推。

3填空题
以下函数使用容斥原理计算从1到N中能被至少一个给定质数整除的数的个数。primes数组中存储互不相同的质数，且均不超过N。请补全代码。

int countDivisible(int N, vector<int>& primes) {
    int n = primes.size();
    int ans = 0;
    for (int mask = 1; mask < (1<<n); ++mask) {
        int bits = __builtin_popcount(mask);
        long long lcm = 1;
        for (int i = 0; i < n; ++i) {
            if (mask & (1<<i)) {
                lcm = lcm / __gcd(lcm, (long long)primes[i]) * primes[i];
            }
        }
        int cnt = N / lcm;
        if (___) {
            ans += cnt;
        } else {
            ans -= cnt;
        }
    }
    return ans;
}
4单选题

某校运动会共有100名学生参加，每人至少参加一个项目。统计得：参加跑步60人，参加跳远50人，参加跳高40人；同时参加跑步和跳远20人，同时参加跑步和跳高20人，同时参加跳远和跳高15人；三项都参加5人。则只参加一个项目的人数为？

A45
B55
C65
D75
5填空题
有n个集合（n≤10），每个集合用整数位掩码表示元素（元素编号0~9，共10种可能）。以下函数使用容斥原理计算这些集合的并集包含的不同元素个数。请补全代码。

int unionCount(int n, int sets[]) {
    int total = 0;
    for (int mask = 1; mask < (1<<n); ++mask) {
        int inter_mask = ___;  // 初始化为全1，表示交集开始取所有位
        for (int i = 0; i < n; ++i) {
            if (mask & (1<<i)) {
                inter_mask &= sets[i];
            }
        }
        int bits = __builtin_popcount(mask);
        int cnt = __builtin_popcount(inter_mask);
        if (bits % 2 == 1) total += cnt;
        else total -= cnt;
    }
    return total;
}