浅谈容斥计数

快速数论变换 · 2025-11-08 21:29:36 · 算法·理论

零·前言

:::align{center} :::

容斥，在 OI 中是一种极其常用的计数方法，通常要结合一定的组合数学知识，并且以一种类似于“反其道而行之”的思想，先对（不）符合要求但是预处理简单的方案进行计算，然后再求出我们所要的答案。

但是实际操作起来还是太困难了，所以我将用一篇文章，让你从什么也不会，变成能掌握简单容斥，不会见到一个容斥计数题就被创飞一次 ~~（但是可以每见到两个计数题被创飞一次）~~。

壹·组合数学基础

想要掌握好容斥，组合数学是必不可少的。一旦缺了组合数学打基础，那么一道容斥可以把你创飞 +\infty 次。

〇、加法原理与乘法原理

加法原理

当你在做一件事情时，它有 n 种方法去解决，而第 i 方法有 m_i 种去做的方式，那么你就有 \sum\limits_{i=1}^nm_i 种解决它的方法。

例如，你从 A 处要去到 B 处，可以选择自驾，坐飞机，~~骑北极熊~~坐火车三种方式，自驾可以走高速公路也可以走下路，飞机有不同的航班，火车也有多种票可选，那么你一共有多少种 A\to B 的方案呢？显然是自驾的方法数 + 飞机航班数 + 火车票方案数。

乘法原理

当你在做一件事情时，发现它能分为 ~~\sout{\lceil\sqrt{n}\rceil} 块~~ n 步解决，每一步有 m_i 种方法可用，那么你就有 \prod\limits_{i=1}^nm_i 种方案解决它。

例如，你现在要从 A 到 B 再到 C，A\to B 有 p 条路线，B\to C 有 q 条路线，根据小学二年级知识，可得 A\to B\to C 共有 p\cdot q 种方案。

一、组合数与排列数

组合数学首先肯定要有组合数啦，不然哪里来的“组合”二字。

排列数

但是首先，我们讲排列数。这玩意在高中数学课本里常写作 A^m_n，可以理解成从一个 n 个元素的数组中区分顺序的选出 m 个元素来，即 \{1,2,3\}，选 \{1,2\} 与选 \{2,1\} 是不一样的；要求一个元素最多被选 1 次，有多少种方案。另一种表述则为 n 个元素中不重复的选出 m 个，求这 m 个元素能排列出的序列数目。

这种 A^m_n 是苏式写法，但你在数学奥赛书上看到的更多是 P^m_n 的写法，这是美式写法。后文都采用美式写法。

从 n 中不重复的选 m 个，我们第一步能选 n 个，第二步能选 n-1 个，……，以此类推，我们第 m 步就能选 n-m+1 个。那么根据乘法原理，我们的方案数就是 \prod\limits_{i=1}^{m}(n-i+1)。

那么我们就得到了：P^m_n=\prod\limits_{k=0}^{m-1}(n-k)，稍加推导可得 P^m_n=\frac{n!}{(n-m)!}。

组合数

在数学课本上，组合数写作 C^m_n，同样是苏式写法；但是我们采用美式写法，写作 \dbinom{n}{m}。

组合数可以看成限制更加严格的排列数。它要求不区分顺序，即 \{1,2,3\}，选 \{1,2\} 与选 \{2,1\} 是一样的；

这时就不能简单地按排列数那样来计数了。因为那样就会出现重复计算。

注意到当你选出这 m 个元素时，它们能排列出 m! 种序列。这时，将原来排列数乘以 \frac{1}{m!}，相当于把重复的多种方案合并到一种。

那么我们可以得到组合数公式：\dbinom{n}{m}=\dfrac{n!}{m!(n-m)!}。

组合数的 \infty 个性质

\dbinom{n}{m}=\dbinom{n-1}{m-1}+\dbinom{n-1}{m}
\dbinom{n}{m}=\dfrac{n-m+1}{m}\dbinom{n-1}{m-1}
\dbinom{n}{m}=\dbinom{n}{n-m}
\sum\limits_{i=0}^n\dbinom{i}{m}=\dbinom{n+1}{m+1}
\sum\limits_{i=0}^n\dbinom{n}{i}=2^n
\sum\limits_{i=0}^k\dbinom{n}{i}\dbinom{m}{k-i}=\dbinom{n+m}{k}
\sum\limits_{i=0}^n(-1)^i\dbinom{n}{i}=[n=0]

组合数的性质实在是太多了，在这里就主要写了一下常用的几个性质 ~~，不然这篇文章就要沦为组合数学专题然后重点内容就要咕咕咕了~~。

例一

组合数学最经典的问题也是动态规划经典问题之一：在一个平面直角坐标系中，n,m\in\N^*,(0,0)\to(n,m)，每步可以向上走一个单位或向右走一个单位，问有多少种走法。

这题很显然的 DP 就是 dp_{n,m}=dp_{n-1,m}+dp_{n,m-1}，但我们要求的是这玩意的公式而不是 DP 式子。

你每次可以选择向上走一步或向右走一步，能够证明，你只能走 n+m 步到达终点；且这 n+m 步中，必须有 n 步是向上走的，则你的方案数为 \dbinom{n+m}{n}。

例二

在一个平面直角坐标系中，n,m\in\N^*,(0,0)\to(n,n)，每步可以向上走一个单位或向右走一个单位，且要求对于你任意时刻的坐标 (x,y)，都要求 x\le y，问有多少种走法。

由于多了一条对你所在坐标的限制，所以不能再像例一一样快速得到简洁优美的式子。

这种问题你在网上一搜，大部分都是将 y=x 的边界线（因为要求你 x\le y 等价于要求你不越过 y=x 这条线）向右平移一个单位，然后将不合规方案从第一个碰到原线的位置绕着新线进行翻转，然后将原来无限制的方案数 \dbinom{2n}{n} 减掉这些不合规的方案总数，得到最终答案就是 \dbinom{2n}{n}-\dbinom{2n}{n-1}=\dfrac{1}{n+1}\dbinom{2n}{n}。

主播主播，这种方法还是太吃操作了，有没有什么易于上手的方法呢？

有的，兄弟有的。我们不妨设 c_k 为在 (k,k) 处第一次触碰到 y=x 这条线时，(0,0)\to(n,n) 的方案数。

这时候问题被 (k,k) 就分解成了两个问题：(0,0)\to(k,k) 与 (k,k)\to(n,n)。

但是你在求解 (0,0)\to(k,k) 这个子问题中不能触碰到 y=x 这条线。那我们不妨将整条线向上平移一个单位，这样就要求了它不会再碰到，那样这一个子问题的方案数就是 c_{k-1}。

而 (k,k)\to(n,n) 这个问题，与原来的问题几乎一样，只不过是范围到缩小了 n-k，则这个子问题的方案数就是 c_{n-k}。

根据乘法原理，可得到 c_k=c_{k-1}\cdot c_{n-k}；接着，运用加法原理，我们最终的方案数就是 c_n=\sum\limits_{k=1}^nc_{k-1}c_{n-k}。

接着上生成函数强推公式，详见这篇文章。

例三

给你一个数 n，求集合 \{(x_1,x_2,\cdots,x_m)|\forall i\in[1,m],x_i\in\N^*\land\sum\limits_{i=1}^mx_i=n\} 大小。

这个问题可以看作：你有 m 个盒子，每个盒子至少放一个小球，共有 n 个小球，问有多少种放法。

这样子这个问题就变得比较明了了，可以使用隔板法，就是用 m-1 个木板，将原来的 n 个球用木板隔开，分为 m 组，每组至少有 1 个小球。

由于要求必须有球，所以我们的木板只能放在小球与小球之间，那就只有 n-1 个空可以放木板，那么我们的答案就是 \dbinom{n-1}{m-1}。

习题：P3266 骗我呢。

贰·认识容斥原理

在数学奥赛书上，你的容斥原理大部分是长这样的。

\left|\bigcup_{i=1}^nS_i\right|=\sum_{T\subseteq(\N^*\cap[1,n])}(-1)^{|T|+1}\left|\bigcap_{k\in T}S_{k}\right|

这是在求 n 个有限集交集的大小。由于直接相加会导致重复元素被多次算入，那么我们就将重复的删掉。但是直接删会导致有一部分被重复计数的元素产生的贡献全部被消除，导致漏数。则我们就要在重新算上这些，……。这样循环往复，就能得到最终交集大小了。

但这个样子在 OI 中还是太不常见了，没有哪个出题人会把这么裸的题扔给你，而且也不太可能是集合的形式。

在 OI 中，常见的容斥有二项式反演、斯特林反演、min-max 反演、莫比乌斯反演等，我们接下来主要讲的是二项式反演。

叁·初试容斥

在 OI 中，容斥最重要的思想就是“反其道而行之”，先计数容易处理的（不）合法方案数，随后套公式计算最终所求的答案。

二项式反演

我通常喜欢将 f_n 表示为恰好 n 个 （不）满足条件时的方案数，一般 f_0 就是答案。而 g_n 则是至多/至少 n 个 （不）满足条件时的方案数。

$$g_n=\sum\limits_{i=0}^n\dbinom{n}{i}f_i\iff f_n=\sum\limits_{i=0}^n(-1)^{n-i}\dbinom{n}{i}g_i$$ $g$ 表示*至少*时的式子。 $$g_k=\sum\limits_{i=k}^n\dbinom{i}{k}f_i\iff f_k=\sum\limits_{i=k}^n(-1)^{i-k}\dbinom{i}{k}g_i$$ 拿至多的例子来证明一下正确性吧。 $$\begin{aligned} f_n&=\sum\limits_{i=0}^n(-1)^{n-i}\dbinom{n}{i}\left[\sum\limits_{j=0}^i\dbinom{i}{j}f_j\right]\\ &=\sum_{i=0}^n\sum_{j=0}^i(-1)^{n-i}\dbinom{n}{i}\dbinom{i}{j}f_j \end{aligned}$$ 接下来跟莫反一样，交换求和顺序。 $$\begin{aligned} f_n&=\sum_{j=0}^n\sum_{i=j}^n(-1)^{n-i}f_j\dbinom{n}{i}\dbinom{i}{j}\\ &=\sum_{j=0}^nf_j\sum_{i=j}^n(-1)^{n-i}\dbinom{n}{i}\dbinom{i}{j}\\ &=\sum_{j=0}^nf_j\sum_{i=j}^n(-1)^{n-i}\dbinom{n-j}{i-j}\dbinom{n}{j}\\ &=\sum_{j=0}^n\dbinom{n}{j}f_j\sum_{i=j}^n(-1)^{n-i}\dbinom{n-j}{i-j}\\ &=\sum_{j=0}^n\dbinom{n}{j}f_j\sum_{k=0}^{n-j}(-1)^{n-j-k}\dbinom{n-j}{k}\\ &=\sum_{j=0}^n\dbinom{n}{j}f_j[n=j]\\ &=f_n \end{aligned}$$ ### 例一求一个长度为 $n$ 的错排个数（错排是指对于长度为 $n$ 的排列 $p$，$\forall 1\le i\le n,p_i\not=i$）。首先有一个简单的递推，即 $D_n=(n-1)(D_{n-1}+D_{n-2})$，但是显然不是我们想要的东西。于是，我们*钦定* $f_k$ 为恰好有 $k$ 个位置满足 $p_i=i$，$g_k$ 为*至少* $k$ 个位置满足 $p_i=i$。很容易看出来 $g_k=\frac{n!}{k!}$，那么直接上公式！ $$f_k=\sum\limits_{i=k}^n(-1)^{i-k}\dbinom{i}{k}g_i$$ $f_0$ 就是我们要的答案，最终经推导可得：$f_0=n!\sum\limits_{i=0}^n\frac{(-1)^i}{i!}$。当然，你可以继续推导得到 $D_n=f_0=\lfloor\frac{n!}{e}+0.5\rfloor$。 ### 例二 **[P5505 [JSOI2011] 分特产](/problem/P5505)** 我们钦定 $f_k$ 为恰好 $k$ 个同学没有特产，$g_k$ 为至少 $k$ 个同学没有特产。如果不区分特产种类的话，那么用隔板法可以得到 $g_k=\dbinom{n}{k}\dbinom{\sum a_i+n-1}{n-1}$，但是光看题目描述我们都能知道要区分种类，那么分别处理一下，然后运用乘法原理，可得 $g_k=\dbinom{n}{k}\prod\limits_{i=1}^m\dbinom{a_i+n-k-1}{n-k-1}

然后套式子就好了。

f_0=\sum\limits_{i=0}^n(-1)^i\dbinom{n}{i}\prod\limits_{j=1}^m\dbinom{a_j+n-i-1}{n-i-1}\\

但由于最后一项恒为 0，让我们把它去掉。

f_0=\sum\limits_{i=0}^{n-1}(-1)^i\dbinom{n}{i}\prod\limits_{j=1}^m\dbinom{a_j+n-i-1}{n-i-1}\\

Code

/*我们所可以自慰的，想来想去，也还是所谓对于将来的希望。

希望是附丽于存在的，有存在，便有希望，有希望，便是光明。*/
#include<bits/stdc++.h>
#define Code using
#define By namespace
#define COB std
Code By COB;
constexpr int p=1e9+7;
unsigned c[5055][5055];
int a[1010],n,m,ans;
__attribute__((constructor))
inline void init(){
    c[0][0]=1;
    for(int i=1;i<=5000;++i){
        c[i][0]=1;
        for(int j=1;j<=i;++j) c[i][j]=(0ull+c[i-1][j-1]+c[i-1][j])%p;
    }
    return;
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=m;++i) cin>>a[i];
    for(int i=0,ret;i<n;++i){
        ret=c[n][i];
        for(int j=1;j<=m;++j) ret=1ull*ret*c[n-i+a[j]-1][n-i-1]%p;
        ans=((0ll+ans+((i&1)? -1:1)*ret)%p+p)%p;
    }
    cout<<ans<<'\n';
    return 0;
}

然而这样的容斥计数还是太平凡了，现在谁家好人会出这种题呢？所以容斥计数正在越来越多的与其他算法结合，尤其是 DP。如P5291 [十二省联考 2019] 希望，在容斥与 DP 的同时还要长链剖分等。

当然，直接就切希望有些不太现实，而且入门文章也不会讲那么深入。

容斥与 DP 结合一般有两种，一种是基于容斥的思想来 DP，另一种则是 DP 预处理 g 求 f，这里只讲第一种，第二种你只要 DP 没问题就行。

例三

P5664 [CSP-S 2019] Emiya 家今天的饭

思考过后，发现本题实际上就是给出一个矩阵，每行只能选一个节点，每列选的节点不能超过所有选的节点的一半，不能不选，给出每个节点的选择方案数，求总方案数。

这个一半的限制~~成功让我在 CSP-S T1 被创飞~~长就是个容斥的样子。我们于是钦定一个节点，出现次数 >\lfloor\frac{n}{2}\rfloor。

那么枚举节点 x，定义 dp_{i,j,k} 为前 i 行中 x 出现 j 次，其他点出现 k 次的方案数。时间复杂度 O(n^3m)，合并状态、优化转移能做到 O(n^2m)。

Code

~~本人的 DP 烂的跟屎一样，而且懒得写了。~~

肆·后记

感觉没有什么可说的，只能祝大家看完我的文章能少被计数题创飞几次吧。