容斥 学习笔记
Visits: 672
小小的知识点,大大的坑。
容斥原理
设集合 $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))$。