容斥原理

· · 个人记录

容斥原理讲义

一、基本概念

容斥原理是组合数学中用于计算多个集合的并集元素数量的原理，通过加法与减法的交替求和实现。其核心思想是通过“先加后调整”的方式避免重复计数。例如：

二、公式表达

一般形式

\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 \cup B| = |A| + |B| - |A \cap B|
  2. 三个集合： |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]硬币购物

共有 4 种硬币。面值分别为 c_1,c_2,c_3,c_4。

某人去商店买东西，去了 n 次，对于每次购买，他带了 d_i 枚 i 种硬币，想购买 s 的价值的东西。请问每次有多少种付款方法。

解题思路：

容斥 + DP

首先看到这个问题，根据经验发现可以通过多重背包解决，但是时间复杂度为 O(ns^2)，非常离谱。

我们先把问题分割成小问题

共有 1 种硬币。面值为c ，不限制使用次数。

那么这就是裸的无限背包，O(n) 即可解决。

加上限制怎么做？直接背包肯定是不行的，我们考虑用总数减去反面。

即 满足条件的方案总数 = 方案总数 - 不满足条件的方案总数

那么问题就转化为了如何求不满足条件的方案总数。我们观察题目性质可以发现，如果我们取了 d_i + 1 个硬币，那么接下来不论怎么取硬币都是非法方案。

所以我们可以想到，强制令体积为 s - c_i * (d_i + 1) 那么所有方案都是非法的，转化为方程也就是

ans = f_s - f_{s - c_i * (d_i + 1)}

试图扩大下这个问题，发现如果我们直接去掉 c_i * (d_i + 1) 还会把其他部分的合法方案给去掉(即同时两个硬币有限制的情况减了两次)。这里设第 i 种硬币的不合法方案集合为 A_i，那么我们就是要求

|A_1 \cup A_2 \cup A_3 \cup A_4|

这就是一个很明显的容斥问题了。

根据容斥原理，我们可以得出

\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}

现在还有一个问题，如何求 |A_1 \cap A_2| ?

还是类似刚才的做法，如果要让这种方案成立，我们就强制把两个硬币全部扣去，即 s - (c_i * (d_i + 1)) - (c_j * (d_j + 1)) 同样可以拓展到 n 个的情况。

对于这个问题，我们在问题最开始时先预处理一遍没有限制的选择方案 f，然后每次求并集直接算 f_{s - (c_i * (d_i + 1)) - (c_j * (d_j + 1))}

#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 ，我们就认为这里是要求 |A_2 \cap A_3|

代码实现

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. 所谓“奇加偶减”，其实是第 i 项的运算和第 i-1 项运算符相反，主要确定第 1 项是啥
  4. 进行第 1 步时，如果发现哪里 RE 了，考虑排查边界问题。

例题2：P1287 盒子与球

我们先来考虑这一种情况：

如果这样，是不是就很好做了呢？

答案就是 m^n，因为每一个小球的决策都不影响其他小球。

那我们再来看这一种情况：

也没有什么难度，我们只要先选出哪些盒子是必须空的，再让剩下的随意分配即可。

答案：\operatorname C_m^k\times(m-k)^n

然后就是重点内容：容斥原理。

我们回到原题，如此考虑：

只需将随意分配的结果个数减去有空盒的即可。

而有空盒的又可以这么分：一个空盒、两个空盒……

所以我们引入这样一个柿子：

\sum_{i=1}^m{(-1)^{i-1}}\operatorname C_m^i(m-i)^n

这就是有空盒的结果个数，是著名的容斥原理的一种应用。

我们只要用 m^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}

这就是最终的结果计算式。

代码如下：

#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;
}

五、总结

容斥原理通过系统性地“加回多减的部分”解决重叠计数问题，需注意：