• 原地址

子集容斥与二项式反演学习笔记

子集容斥

公式：

$$\begin{align*} g(S)&=\sum\limits_{T\subseteq S}f(T)\\ f(S)&=\sum\limits_{T\subseteq S}(-1)^{\left|S\right|-\left|T\right|}g(T) \end{align*}$$

证明：

$$\begin{align*} &\sum\limits_{T\subseteq S}(-1)^{\left|S\right|-\left|T\right|}g(T)\\ =&\sum\limits_{T\subseteq S}(-1)^{\left|S\right|-\left|T\right|}\sum\limits_{R\subseteq T}f(R)\\ =&\sum\limits_{R\subseteq T}f(R)\sum\limits_{R\subseteq T\subseteq S}(-1)^{\left|S\right|-\left|T\right|} \end{align*}$$

若 ，则 。

二项式反演

公式：

$$\begin{align*} g_{i}&=\sum_{k\ge i}\dbinom{k}{i}f_k\\ f_{i}&=\sum_{k\ge i}\dbinom{k}{i}(-1)^{k-i}g_k \end{align*}$$

证明：

$$\begin{align*} &\sum_{k\ge i}\dbinom{k}{i}(-1)^{k-i}g_k\\ =&\sum_{k\ge i}\dbinom{k}{i}(-1)^{k-i}\sum_{j\ge k}\dbinom{j}{k}f_j\\ =&\sum_{j\ge i}f_j\sum_{i\le k \le j}\dbinom{k}{i}\dbinom{j}{k}(-1)^{k-i}\\ =&\sum_{j\ge i}f_j\sum_{i \le k \le j}\frac{k!}{i!(k-i)!}\frac{j!}{k!(j-k)!}(-1)^{k-i}\\ =&\sum_{j\ge i}f_j\frac{j!}{i!}\sum_{i \le k \le j}\frac{1}{(k-i)!(j-k)!}(-1)^{k-i}\\ =&\sum_{j\ge i}f_j\frac{j!}{i!(j-i)!}(1-1)^{k-i}\\ =&f_j \end{align*}$$

同理：

$$\begin{align*} g_i&=\sum_{k\le i}\dbinom{i}{k}f_k\\ f_i&=\sum_{k\le i}\dbinom{i}{k}(-1)^{i-k}g_k \end{align*}$$

例题：

黑暗前的幻想乡

题目大意：

给定一个无向图和每个公司能造的边，要求统计每个公司恰好建造一条边的生成树数量。

前置知识：

• [ ] 子集容斥
• [ ] 矩阵树定理（生成树计数）

思路

在没有公司限制的情况下，我们只需要跑一边生成树计数即可（挖个坑）。在加上限制条件之后，我们可以考虑将参加建造的公司看成一个子集 ，求出每个子集对应的生成树数量 ，最后子集容斥即可。