容斥 学习笔记

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

容斥原理

设集合 $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))$。