容斥原理与二项式反演

容斥原理

对于集合 $S_1, S_2, \ldots, S_n$ :

$\begin{aligned} \left|\bigcup_{i=1}^{n}S_i\right|=&\sum_{i}|S_i|-\sum_{i<j}|S_i\cap S_j|+\sum_{i<j<k}|S_i\cap S_j\cap S_k|+\cdots+(-1)^{n-1}|S_1\cap\cdots\cap S_n| \end{aligned}$

也就是说，对于满足若干个性质中至少一个的元素，可以用同时满足若干个性质的元素个数进行容斥（满足一个的 - 满足两个的 + 满足三个的……）

如果对于上式稍加修改，我们也能得出集合交集的容斥公式：

$\begin{aligned} \left|\bigcap_{i=1}^{n}S_i\right|=&|U|-\left|\bigcup_{i=1}^n\overline{S_i}\right|\\ =&|U|-\sum_{i}|\overline{S_i}|+\sum_{i<j}|\overline{S_i}\cap \overline{S_j}|-\sum_{i<j<k}|\overline{S_i}\cap \overline{S_j}\cap \overline{S_k}|+\cdots+(-1)^{n}|\overline{S_1}\cap\cdots\cap \overline{S_n}| \end{aligned}$

也就是说，对于全部满足若干个性质的元素，可以用同时不满足若干个性质的元素个数进行容斥（所有 - 不满足一个的 + 不满足两个的 - 不满足三个的……）

二项式反演

形式

形式一

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

从组合意义上看，这个式子的含义可以理解为 $f(n)$ 是从 $n$ 个元素中选出 $i$ 个满足条件的方案数，而 $g(n)$ 是恰好有 $n$ 个满足的方案数。

形式二

$f(n) = \sum_{i=n}^m \dbinom i n g(i) \iff g(n)=\sum_{i=n}^m \dbinom i n (-1)^{i-n} f(i)$

从组合意义上看，这个式子的含义可以理解为 $f(n)$ 是钦定有 $n$ 个满足，其他随便的方案数，而 $g(n)$ 是恰好有 $n$ 个满足的方案数。

例题

P4071 [SDOI2016] 排列计数

求长度为 $n$ ，恰好有 $m$ 个位置满足 $a_i=i$ 的排列个数。
多测， $T\le 5\times 10^5, n,m\le 10^6$ 。

考虑利用形式二进行二项式反演。

钦定有 $k$ 个位置满足 $a_i=i$ 的排列个数 $f(k)=\dbinom n k (n-k)! = \dfrac{n!}{k!}$ 。
则要求的式子

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