上善若水任方圆,以其不争掌仙人

初探容斥原理

2018-09-13 18:56:47


如果有错误,欢迎打脸

(由于太懒还没)同步于我的博客

有时候我们要按照类别来统计数量,可能有的元素属于多个不同的类别。在计数时,必须注意没有重复,没有遗漏。为了使重叠部分不被重复计算,可以利用容斥原理。

一些前置技能

二项式定理

$$\sum_{i=0}^{n}{n \choose i}a^ib^{n-i}=(a+b)^n$$

交换求和号

这个不太好描述……具体问题具体分析……就举个例子……

$$\sum_{i=0}^{n} f(i) \sum_{j=0}^{i} g(j)h(i,j)=\sum_{j=0}^{n} g(j) \sum_{i=j}^{n} f(i)h(i,j)$$

交换后只要保证每一组乘积与之前一一对应即可

组合数经典公式

$${n \choose i}={n-1 \choose i}+{n-1 \choose i-1}$$

公式化的理解:手动拆开式子然后约分

从组和数上的意义理解:从 $n$ 个物品中挑选出 $i$ 个物品,相当于考虑是否最终挑选出第 $i$ 个物品,如果不挑选出,那么方案数为 ${n-1 \choose i}$ ,如果挑选出,那么方案为 ${n-1 \choose i-1}$

这个公式十分有用……如果是一个组合数乘上一个 $-1$ 的若干次幂后求和的形式,可以直接大力拆式子,然后一正一负就消掉了……

参考文献

WerKeyTom_FTD 《容斥的原理及广义应用》

什么是容斥

从一个简单的例题说起

有 $k$ 种属性,你有一个函数 $f(S)$ ,可以快速得知至少满足 $S$ 属性的集合的物品个数,同时定义 $f(\emptyset)=0$

现在你想知道至少有一种属性的物品的个数, $k \le 20$

可能小学老师们告诉过你,答案就是

$$\sum_{S \subseteq U}f(S)(-1)^{|S|+1}$$

通过文氏图,可以轻而易举的得知在 $k \le 3$ 的时候是十分清晰易懂的,那么在 $k$ 更高维的情况下,不妨证明一下为什么这个式子是对的

考虑每一个物品,假设它有 $n$ 个属性,当然在 $n=0$ 的时候只会被 $f(\emptyset)$ 枚举到,而且对答案的贡献为 $0$

如果 $n \ge 1$ ,那么可以枚举一下它的属性会被哪些组合枚举到,既

$$\begin{aligned}\sum_{i=1}^{n} {n \choose i} (-1)^{i+1}&=-(\sum_{i=1}^{n} {n \choose i} (-1)^{i})\\&=-((1-1)^n-1)\\&=1\end{aligned}$$

因此这个物品如果至少有一个属性的话那么一定会被只对答案产生 $1$ 的贡献

也许对容斥有了一些感性的理解了吧

一般化的经典容斥

首先需要有一个属性集合 $k$ ,然后假设有一个可以查询至少满足属性集合 $S$ 的物品个数的函数 $q(S)$

同时还有一个函数 $g(k)$ ,对于一个有 $k$ 个属性的物品,它会对答案产生 $g(k)$ 的贡献

同时确定一个容斥系数 $f(x)$ ,使得答案为 $\sum_{S \subseteq U}q(S)f(|S|)$

此时看一下每一个物品会怎么对答案产生贡献的(假设这个物品有 $n$ 个属性):

$$\sum_{i=1}^{n} {n \choose i} f(i)=g(n)$$

如果允许 $O(n^2)$ 的时间复杂度的话,可以直接通过递推来计算出 $f(x)$

既假设知道了 $f(1) \sim f(n)$ ,现在要计算 $f(n+1)$ ,根据定义有

$$\sum_{i=1}^{n+1} {n + 1 \choose i} f(i)=g(n+1) \Rightarrow f(n+1)=g(n+1)-\sum_{i=1}^{n} {n+ 1\choose i} f(i)$$

于是就可以打表找规律了!

计算容斥系数

然而如果需要快速计算 $f(x)$ 呢?

发现上面那个式子比较像卷积的形式,定义 $f(0)=0$

也就是说

$$\begin{aligned}g(n)&=\sum_{i=1}^{n} {n \choose i} f(i) \\&=\sum_{i=0}^{n}\frac{n!}{i!(n-i)!}f(i) \\&=n!\sum_{i=0}^{n}\frac{1}{(n-i)!}\frac{f(i)}{i!} \\\end{aligned}$$

整理一下就是

$$\frac{g(n)}{n!}=\sum_{i=0}^{n}\frac{1}{(n-i)!}\frac{f(i)}{i!}$$

设 $G(x)=\sum\limits_{i=0}^{\infty}x^i\frac{g(i)}{i!},H(x)=\sum\limits_{i=0}^{\infty}x^i\frac{1}{i!}=e^x,F(x)=\sum\limits_{i=0}^{\infty}x^i\frac{f(i)}{i!}$

则 $G(x)=H(x)F(x)$ ,也就是 $F(x)=\frac{G(x)}{H(x)}=e^{-x}G(x)$

于是可以用优秀的多项式求逆算法在 $O(n \log n)$ 的时间复杂度内解决了!

当然还有一种优秀的反演方法……并没有学会……

可以在WerKeyTom_FTD 《容斥的原理及广义应用》中看到

一些简单的应用

统计人数问题

已知在某场比赛中,一共有 $\{1,2,3\}$ 这三道题,同时你可以查询 $f(S)$ ,会返回至少切了集合 $S$ 的题的人的个数,问有多少人至少切了一道题?

根据上面的推导,可以知道答案就是

$$f(\{1\})+f(\{2\})+f(\{3\})-f(\{1,2\})-f(\{1,3\})-f(\{2,3\})+f(\{1,2,3\})$$

错排问题

问 $1 \sim n$ 的所有排列 $a$ 中,满足 $a_i \not= i$ 的排列数

对于不等于的限制似乎不太好做,但对于等于的限制是十分好做的:如果有 $x$ 个位置满足 $a_i=i$ ,那么其余位置的方案数为 $(n-x)!$

所以可以枚举至少哪些位置是不合法的,然后容斥一下

设 $f(n)$ 表示 $n$ 个数的错排个数,则

$$ \begin{aligned} f(n) &=\sum_{i=0}^{n}(-1)^{i} {n \choose i} (n-i)! \\ &=\sum_{i=0}^{n}(-1)^i \frac{n!}{i!(n-i)!}(n-i)! \\ &=\sum_{i=0}^{n}(-1)^i \frac{n!}{i!} \\ &=n\sum_{i=0}^{n}(-1)^i \frac{(n-1)!}{i!} \\ &=(-1)^{n} \frac{n!}{n!} + n\sum_{i=0}^{n-1}(-1)^i \frac{(n-1)!}{i!} \\ &=(-1)^{n} + nf(n-1) \\ \end{aligned} $$

关于第一行的说明:

首先需要枚举一下有多少个位置是不满足错排的,这个是 $\sum_{i=0}^{n}$

其次需要一个容斥系数,为 $(-1)^i$

之后枚举那些位置不满足错排,这是 ${n \choose i}$

对于剩下的位置可以随意放,也就是 $(n-i)!$

证明一下正确性:

假设一个排列有 $k$ 的地方满足 $a_i = i$ ,既要求对答案的贡献为 $[k=0]$

那么实际对答案的贡献为: $$ \begin{aligned} \sum_{i=0}^{k}{k \choose i}(-1)^i \end{aligned} $$ 上面那个式子在 $k=0$ 的时候对答案的贡献为 $1$ ,满足题意,以下考虑在 $k \ge 1$ 的情况下对答案的贡献 $$ \begin{aligned} \sum_{i=0}^{k}{k \choose i}(-1)^i &=(1-1)^k\\&=0\end{aligned} $$

那如果要求恰好 $k$ 个位置满足错排呢?

枚举一下哪些位置不满足错排,显然剩下的位置只能唯一确定,既 ${n \choose k}f(k)$

那如果要求至少 $k$ 个位置满足错排呢( $k \ge 1$ )?

同理,答案就是 $\sum_{i=1}^{k} {n \choose i}f(i)$

方程的解问题

给定一个方程 $\sum_{i=1}^{n}x_i=b$ ,问非负整数的个数

通过组合数学,可以得知解的个数为 ${n+b-1 \choose n-1}$

一个简单粗暴的证明:

相当于将 $b$ 个 $1$ 分割成 $n$ 份,允许某份是空的,问方案数

考虑设置 $n$ 个特殊点,如果第 $i$ 个特殊点被选中了,则第 $i$ 堆为空

然后将 $b$ 个 $1$ 分成若干份,依次对应非空的 $x_i$

于是解的个数就是 ${n+b-1 \choose n-1}$

然而如果对于每一个 $x_i$ 都有限制呢?诸如 $l_i \le x_i \le r_i$

设 $y_i=x_i-l_i$ ,也就是 $0 \le y_i \le r_i-l_i$ ,这样对于每一个非负整数解 $y_i$ ,都有一个非负整数 $x_i$ 与之对应

换句话说问题转化为了限制诸如 $0 \le x_i \le k_i$ 的形式

考虑容斥,每次枚举哪些 $x_i$ 不满足限制,既 $x_i \ge k_i+1$ ,然后配上正确的容斥系数

如何让 $x_i$ 不满足限制?设 $x_i'=x_i+k_i+1$ ,然后把 $x_i'$ 替换 $x_i$ 就行了

设 $f(S)$ 表示集合 $S$ 的变量不满足限制的方案数,显然有

$$ f(S)={n+b-1-\sum_{i \in S}(k_i+1)\choose n-1} $$

同时对于答案 $T$ ,有

$$ T=\sum_{S \subseteq U}(-1)^{|S|}f(S)=\sum_{S \subseteq U}(-1)^{|S|}{n+b-1-\sum_{i \in S}(k_i+1)\choose n-1} $$

字符串匹配问题

SDOI2009 Bill的挑战

有 $n$ 个长度相同的模板串,用?表示通配符(可以匹配任何字符),给出一个整数 $k$ ,求恰好匹配 $k$ 个模板串的字符串的个数

一般化的题目描述:

有 $n$ 个属性,求恰好满足 $k$ 个属性的物品个数

你有一个函数 $q(S)$ ,可以快速算出至少满足属性集合 $S$ 的物品个数(保证每个物品最多只会被统计一次)

设 $f(S)$ 表示只满足属性集合 $S$ 的物品的个数,那么答案就是 $\sum_{S \subseteq U \wedge |S| = k}f(S)$

设 $f(S)=\sum\limits_{S \subseteq P \subseteq U}q(P)g(|P|)$ ,其中 $|S|=k$ ,显然有 $g(x)=(-1)^{x-k}$

证明:

对于一个物品 $t$ ,假设它的属性集合为 $Q$ ,且 $S \subseteq Q$ ,且 $|Q|=k+u$

那么它对 $f(S)$ 的贡献是 $$\sum_{i=0}^{u}{u \choose i}(-1)^{i}=(-1+1)^{u}=[u=0]$$

也就是说 $f(S)=\sum\limits_{S \subseteq P \subseteq U}q(P)(-1)^{|P|-k}$

也就是说

$$\begin{aligned}T&=\sum\limits_{S \subseteq U \wedge |S| = k}f(S) \\&=\sum\limits_{S \subseteq U \wedge |S| = k} \sum_{S \subseteq P \subseteq U}q(P)(-1)^{|P|-k} \\&=\sum\limits_{P \subseteq U \wedge |P| \ge k} q(P)(-1)^{|P|-k}{|P| \choose k}\end{aligned}$$

于是就做完了……

$q(S)$ 的话可以直接判断一下是否有冲突,如果没有冲突的话求一下有多少个位置是用?填充的,假设有 $x$ 个位置用?填充,那么 $q(S)=2^x$

如果扩展一下这道题,将“恰好”改成“至少”呢?

设 $T(k)$ 表示恰好匹配 $k$ 个字符串的方案数, $Q(k)$ 表示至少匹配 $k$ 个字符串的方案数,则

$$ \begin{aligned} Q\left(k\right) &=\sum_{i=k}^{n}T\left(i\right) \\ &=\sum_{i=k}^{n}\sum\limits_{P \subseteq U \wedge |P| \ge i} q\left(P\right)\left(-1\right)^{|P|-i}{|P| \choose i} \\ &=\sum_{P \subseteq U \wedge |P| \ge k} q\left(P\right)\sum_{i=k}^{|P|}\left(-1\right)^{|P|-i} {|P| \choose i} \\ &=\sum_{P \subseteq U \wedge |P| \ge k} q\left(P\right)\left(-1\right)^{1-|P|}\sum_{i=k}^{|P|}\left(-1\right)^{i} {|P| \choose i} \\ &=\sum_{P \subseteq U \wedge |P| \ge k} q\left(P\right)\left(-1\right)^{1-|P|}\sum_{i=k}^{|P|}\left(-1\right)^{i} \left({|P| - 1 \choose i}+{|P| -1 \choose i-1}\right) \\ &=\sum_{P \subseteq U \wedge |P| \ge k} q\left(P\right)\left(-1\right)^{1-|P|}\left(\left(\sum_{i=k+1}^{|P|+1}\left(-1\right)^{i-1} {|P| - 1 \choose i-1}\right)+\left(\sum_{i=k}^{|P|}\left(-1\right)^{i}{|P|-1 \choose i-1}\right)\right) \\ &=\sum_{P \subseteq U \wedge |P| \ge k} q\left(P\right)\left(-1\right)^{1-|P|}\left(\left(-1^{|P|}\right){|P|-1 \choose |P| }+\left(-1\right)^{k}{|P|-1 \choose k-1}\right) \\ &=\sum_{P \subseteq U \wedge |P| \ge k} q\left(P\right)\left(-1\right)^{|P|-k}{|P|-1 \choose k-1} \\ &=\sum_{P \subseteq U \wedge |P| \ge k} q\left(P\right)\left(-1\right)^{|P|-k}{|P|-1 \choose |P|-k} \\ \end{aligned} $$

这个似乎没什么解释的……将一个式子套到另一个式子后,直接化简……

鸣谢

  • 感谢 _rqy 对本文出现的一些错误进行指出