专栏文章

容斥原理

EEDG_AKUYTRE
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miocuwci
此快照首次捕获于
2025/12/02 17:07
3 个月前
此快照最后确认于
2025/12/02 17:07
3 个月前
查看原文

容斥原理讲义

一、基本概念

容斥原理是组合数学中用于计算多个集合的并集元素数量的原理，通过加法与减法的交替求和实现。其核心思想是通过“先加后调整”的方式避免重复计数。例如：
  • 两个集合的并集大小为 ‌|A| + |B| - |A∩B|‌（减去交集消除重复计数）
  • 推广到n个集合时，需依次处理所有可能的交集的奇偶次叠加（奇数次加，偶数次减）

二、公式表达

一般形式

∣⋃i=1nAi∣=∑i=1n∣Ai∣−∑1≤i<j≤n∣Ai∩Aj∣+⋯+(−1)n+1∣A1∩⋯∩An∣\left| \bigcup_{i=1}^n A_i \right| = \sum_{i=1}^n |A_i| - \sum_{1 \leq i < j \leq n} |A_i \cap A_j| + \cdots + (-1)^{n+1} |A_1 \cap \cdots \cap A_n|

常见特例

  1. 两个集合：
    ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣|A \cup B| = |A| + |B| - |A \cap B|
  2. 三个集合：
    ∣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|

三、应用场景

  1. ‌排列组合问题‌
    • 如计算受限条件下的排列数（如“至少一个条件不满足”的情况）。
  2. ‌概率计算‌
    • 求多个事件并集的概率（如摸牌游戏中同时摸到两种花色的概率）。
  3. ‌数论问题‌
    • 统计区间内与某数互质的数的个数。
  4. ‌容斥优化算法‌
    • 如动态规划中排除非法状态的计数

四、洛谷例题解析

例题1：P1450 硬币购物

‌问题简述‌
P1450 [HAOI2008]硬币购物
共有 44 种硬币。面值分别为 c1,c2,c3,c4c_1,c_2,c_3,c_4。
某人去商店买东西，去了 nn 次，对于每次购买，他带了 did_i 枚 ii 种硬币，想购买 ss 的价值的东西。请问每次有多少种付款方法。

解题思路：

容斥 + DP
首先看到这个问题，根据经验发现可以通过多重背包解决，但是时间复杂度为 O(ns2)O(ns^2)，非常离谱。
我们先把问题分割成小问题
共有 11 种硬币。面值为cc ，不限制使用次数。
那么这就是裸的无限背包，O(n)O(n) 即可解决。
加上限制怎么做？直接背包肯定是不行的，我们考虑用总数减去反面。
即 满足条件的方案总数 = 方案总数 - 不满足条件的方案总数
那么问题就转化为了如何求不满足条件的方案总数。我们观察题目性质可以发现，如果我们取了 di+1d_i + 1 个硬币，那么接下来不论怎么取硬币都是非法方案。
所以我们可以想到，强制令体积为 s−ci∗(di+1)s - c_i * (d_i + 1) 那么所有方案都是非法的，转化为方程也就是
ans=fs−fs−ci∗(di+1)ans = f_s - f_{s - c_i * (d_i + 1)}
试图扩大下这个问题，发现如果我们直接去掉 ci∗(di+1)c_i * (d_i + 1) 还会把其他部分的合法方案给去掉(即同时两个硬币有限制的情况减了两次)。这里设第 ii 种硬币的不合法方案集合为 AiA_i，那么我们就是要求
∣A1∪A2∪A3∪A4∣|A_1 \cup A_2 \cup A_3 \cup A_4|
这就是一个很明显的容斥问题了。
根据容斥原理，我们可以得出
∣A1∪A2∪A3∪A4∣=(∣A1∣+∣A2∣+∣A3∣+∣A4∣)−(∣A1∩A2∣+∣A1∩A3∣+∣A1∩A4∣+∣A2∩A3∣+∣A2∩A4∣+∣A3∩A4∣)+(∣A1∩A2∩A3∣+∣A1∩A2∩A4∣+∣A2∩A3∩A4∣)−∣A1∩A2∩A3∩A4∣\begin{aligned} &|A_1 \cup A_2 \cup A_3 \cup A_4| \\ &= (|A_1| + |A_2| + |A_3| + |A_4|) \\ &- (|A_1 \cap A_2| + |A_1 \cap A_3| +|A_1 \cap A_4| + |A_2 \cap A_3|+ |A_2 \cap A_4|+ |A_3 \cap A_4|)\\ &+ (|A_1 \cap A_2 \cap A_3| + |A_1 \cap A_2 \cap A_4| + |A_2 \cap A_3 \cap A_4|)\\ &- |A_1 \cap A_2 \cap A_3 \cap A_4| \end{aligned}
现在还有一个问题，如何求 ∣A1∩A2∣|A_1 \cap A_2| ?
还是类似刚才的做法，如果要让这种方案成立，我们就强制把两个硬币全部扣去，即 s−(ci∗(di+1))−(cj∗(dj+1))s - (c_i * (d_i + 1)) - (c_j * (d_j + 1)) 同样可以拓展到 nn 个的情况。
对于这个问题，我们在问题最开始时先预处理一遍没有限制的选择方案 ff，然后每次求并集直接算 fs−(ci∗(di+1))−(cj∗(dj+1))f_{s - (c_i * (d_i + 1)) - (c_j * (d_j + 1))}
CPP
#include <iostream>
#include <cstdio>
#include <cstring>
#define int long long
using namespace std;
const int MAXN=1e5+10;
int dp[MAXN],c[5],d[5],s;
int f(int x) {
    return c[x]*(d[x]+1);
}
signed main(){
    cin>>c[1]>>c[2]>>c[3]>>c[4];
    dp[0]=1;
    for(int i=1;i<=4;i++)
        for(int j=c[i];j<=MAXN;j++)
                dp[j]+=dp[j-c[i]];
                
    int T;
    cin>>T;
    while(T--) {
        cin>>d[1]>>d[2]>>d[3]>>d[4]>>s;
        int ans=dp[s];
        if(s>=f(1))ans-=dp[s-f(1)];
        if(s>=f(2))ans-=dp[s-f(2)];
        if(s>=f(3))ans-=dp[s-f(3)];
        if(s>=f(4))ans-=dp[s-f(4)];
        if(s>=f(1)+f(2))ans+=dp[s-f(1)-f(2)];
        if(s>=f(1)+f(3))ans+=dp[s-f(1)-f(3)];
        if(s>=f(1)+f(4))ans+=dp[s-f(1)-f(4)];
        if(s>=f(2)+f(3))ans+=dp[s-f(2)-f(3)];
        if(s>=f(2)+f(4))ans+=dp[s-f(2)-f(4)];
        if(s>=f(3)+f(4))ans+=dp[s-f(3)-f(4)];
        if(s>=f(1)+f(2)+f(3))ans-=dp[s-f(1)-f(2)-f(3)];
        if(s>=f(1)+f(2)+f(4))ans-=dp[s-f(1)-f(2)-f(4)];
        if(s>=f(1)+f(3)+f(4))ans-=dp[s-f(1)-f(3)-f(4)]; 
        if(s>=f(2)+f(3)+f(4))ans-=dp[s-f(2)-f(3)-f(4)];
        if(s>=f(1)+f(2)+f(3)+f(4))ans+=dp[s-f(1)-f(2)-f(3)-f(4)];
        cout<<ans<<endl;
    }
    return 0;
}
简化：通过枚举子集来快速求解，比如说 5 对应的 4 位二进制表示为 0110 ，我们就认为这里是要求 ∣A2∩A3∣|A_2 \cap A_3|
代码实现
CPP
for (int i = 0;i < 16;++i) {
    ll siz = 0,k = 0,tmp = 0,tot = 1;
    ll p = i;
    while (p) {
        if (p & 1) {
            tmp += c[tot] * (d[tot] + 1);
            //计算c_i * (d_i + 1)
            ++siz;
            //统计当前有多少个
        }
        ++tot,p >>= 1;
    }
    if (siz % 2) k = -1;
    else k = 1;
    //奇加偶减
    if (s - tmp < 0) continue;
    //排除非法方案
    ans += k * f[s-tmp];
}
于是这题就做完了。
总结：
  1. 如果正面思考不通，尝试用整体去掉反面来计算答案
  2. 统计方案时出现重复部分，用容斥原理来处理
  3. 所谓“奇加偶减”，其实是第 ii 项的运算和第 i−1i-1 项运算符相反，主要确定第 1 项是啥
  4. 进行第 1 步时，如果发现哪里 RE 了，考虑排查边界问题。

例题2：P1287 盒子与球

nn 个球，mm 个盒子，彼此互不相同，求将球全部放入盒中的方案数，不允许空盒。
我们先来考虑这一种情况：
nn 个球，mm 个盒子，彼此互不相同，求将球全部放入盒中的方案数，允许空盒。
如果这样，是不是就很好做了呢？
答案就是 mnm^n，因为每一个小球的决策都不影响其他小球。
那我们再来看这一种情况：
nn 个球，mm 个盒子，彼此互不相同，求将球全部放入盒中的方案数，至少 kk 个空盒。
也没有什么难度，我们只要先选出哪些盒子是必须空的，再让剩下的随意分配即可。
答案：C⁡mk×(m−k)n\operatorname C_m^k\times(m-k)^n
然后就是重点内容：容斥原理。
我们回到原题，如此考虑：
只需将随意分配的结果个数减去有空盒的即可。
而有空盒的又可以这么分：一个空盒、两个空盒……
所以我们引入这样一个柿子：
∑i=1m(−1)i−1C⁡mi(m−i)n\sum_{i=1}^m{(-1)^{i-1}}\operatorname C_m^i(m-i)^n
这就是有空盒的结果个数，是著名的容斥原理的一种应用。
我们只要用 mnm^n 减去这个柿子，就是我们的答案。
但是，这两个东西可以合在一起：
mn−∑i=1m(−1)i−1Cmi(m−i)n= mn+∑i=1m(−1)iCmi(m−i)n= (−1)0C⁡m0(m−0)n+∑i=1m(−1)iC⁡mi(m−i)n= ∑i=0m(−1)iC⁡mi(m−i)n\begin{aligned}&m^n-\sum_{i=1}^m{(-1)^{i-1}}\mathrm C_m^i(m-i)^n \\ =\ & m^n+\sum_{i=1}^m{(-1)^i}\mathrm C_m^i(m-i)^n \\ =\ &(-1)^0\operatorname C_m^0(m-0)^n+\sum_{i=1}^m{(-1)^i}\operatorname C_m^i(m-i)^n \\ =\ &\sum_{i=0}^m{(-1)^i}\operatorname C_m^i(m-i)^n \\\end{aligned}
这就是最终的结果计算式。
代码如下：
CPP
#include<bits/stdc++.h>
using namespace std;
long long qpow(long long a,long long n){
    long long ans=1;
    while(n){
        if(n%2)ans*=a;
        a*=a;
        n>>=1;
    }
    return ans;
}
long long C(long long a,long long b){
    long long ans=1;
    for(long long i=a-b+1;i<=a;++i)ans=ans*i;
    for(long long i=1;i<=b;++i)ans=ans/i;
    return ans;
}
int main(){
    long long a,b;
    cin>>a>>b;
    long long ans=0;
    for(long long i=0;i<b;++i){
        if(i&1)ans-=C(b,i)*qpow(b-i,a);
        else ans+=C(b,i)*qpow(b-i,a);
    }
    cout<<ans;
    return 0;
}

五、总结

容斥原理通过系统性地“加回多减的部分”解决重叠计数问题，需注意：
  • ‌公式记忆‌：奇加偶减。
  • ‌应用技巧‌：将问题转化为集合的并/交运算。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...