容斥 学习笔记

作者: xht37 分类: 笔记 发布时间: 2020-05-06 21:48

点击数:146

小小的知识点,大大的坑。

容斥原理

设集合 $S_{1\dots n}$,有
$$
\left| \bigcup_{i=1}^n S_i \right| = \sum_{k=1}^n(-1)^{k+1}\sum_{1\le p_1 < p_2 < \cdots < p_k \le n} \left| \bigcap_{i=1}^k S_{p_i} \right|
$$

多重集组合数

设集合 $S$ 是由 $k$ 个不同元素组成的大小为 $n$ 的可重集合,对于 $i \in [1,k]$,第 $i$ 个元素有 $n_i$ 个。
对于 $r \in [0,n]$,求从 $S$ 中选出 $r$ 个元素组成一个多重集的方案数。

答案为
$$
\sum_{t=0}^k (-1)^t \sum_{1 \le p_1 < p_2 < \cdots < p_t \le k} \binom {r + k – 1 – t – \sum_{i=1}^{t}n_{p_i}}{k – 1}
$$

反演

反演就是一些特殊的容斥。

欧拉反演

$$
n = \sum_{d|n} \varphi(d)
$$

莫比乌斯反演


$$
f(n) = \sum_{d|n} g(d)
$$

$$
g(n) = \sum_{d|n}\mu(\frac nd)f(d)
$$

$$
f(d) = \sum_{d|n} g(n)
$$

$$
g(d) = \sum_{d|n} \mu(\frac nd) f(n)
$$

子集反演


$$
f(S) = \sum_{T \subseteq S} g(T)
$$

$$
g(S) = \sum_{T \subseteq S} (-1)^{|S|-|T|} f(T)
$$


$$
f(S) = \sum_{S \subseteq T} g(T)
$$

$$
g(S) = \sum_{S \subseteq T}(-1)^{|T|-|S|}f(T)
$$

多重子集反演

对于集合 $S$,定义 $\mu(S)$:若 $S$ 存在重复元素则为 $0$,否则为 $(-1)^{|S|}$。


$$
f(S) = \sum_{T \subseteq S} g(T)
$$

$$
g(S) = \sum_{T \subseteq S} \mu(S – T)f(T)
$$

$$
f(S) = \sum_{S \subseteq T} g(T)
$$

$$
g(S) = \sum_{S \subseteq T} \mu(T – S)f(T)
$$
莫比乌斯反演是多重子集反演的特殊形式。

二项式反演


$$
f(n) = \sum_{k=0}^n \binom nk g(k)
$$

$$
g(n) = \sum_{k=0}^n (-1)^{n-k} \binom nk f(k)
$$

二项式反演是子集反演的特殊形式。

【例题】BZOJ2839 集合计数

设交集至少有 $i$ 个元素的方案数为 $f(i)$,则
$$
f(i) = \binom ni \left(2^{2^{n-i}}-1\right)
$$
设交集恰好有 $i$ 个元素的方案数为 $g(i)$,则
$$
f(i) = \sum_{j = i}^n \binom ji g(j)
$$
二项式反演一下,则
$$
g(i) = \sum_{j=i}^n (-1)^{j-i} \binom ji f(j)
$$
因此答案为
$$
g(k) = \sum_{i=k}^n (-1)^{i-k} \binom ik \binom ni \left(2^{2^{n-i}}-1\right)
$$
时间复杂度 $\mathcal O(n)$。

最值反演 / Min-Max 容斥

对于一个集合 $S$,有
$$
\max(S) = \sum_{T \subseteq S}(-1)^{|T|+1} \min(T)
$$

$$
\min(S) = \sum_{T \subseteq S}(-1)^{|T|+1} \max(T)
$$

这两个式子在期望下也成立。

【例题】LOJ2127 按位或

$\max(S)$ 表示 $S$ 被全部或为 $1$ 的期望时间,$\min(S)$ 表示 $S$ 被或到至少一位为 $1$ 的期望时间,则有
$$
\begin{aligned}ans &= \max(S) \\&= \sum_{T \subseteq S}(-1)^{|T|+1} \min(T) \\&= \sum_{T \subseteq S}(-1)^{|T|+1} \frac1 {1-\sum_{X \subseteq (U-T)} p(X)} \\\end{aligned}
$$
FWT 即可,时间复杂度 $\mathcal O(2^nn)$。

推广到 kth

$$
kth\max(S) = \sum_{T \subseteq S}(-1)^{|T|+k} \binom {|T|-1}{k-1} \min(T)
$$

$$
kth\min(S) = \sum_{T \subseteq S}(-1)^{|T|+k} \binom {|T|-1}{k-1} \max(T)
$$

这两个式子在期望下也成立。

【例题】P4707 重返现世

$$
\begin{aligned}ans &= kth\max(S) \\&= \sum_{T \subseteq S}(-1)^{|T|+k} \binom {|T|-1}{k-1} \min(T) \\&= \sum_{T \subseteq S}(-1)^{|T|+k} \binom {|T|-1}{k-1} \frac m{\sum_{i\in T}p(i)} \\\end{aligned}
$$

然后可以 DP,时间复杂度 $\mathcal O(nm(n-k))$。

发表评论

电子邮件地址不会被公开。 必填项已用*标注