本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-05 20:35:13

容斥原理

设 $U$ 中元素有 $n$ 种不同的属性，而第 $i$ 种属性称为 $P_i$，拥有属性 $P_i$ 的元素构成集合 $S_i$，那么

$$\left | \bigcup {i=1}^n s_i \right | =\sum{m=1}^{n} (-1)^{m-1} \sum_{a_i<a_{i+1}}^{} \left | \bigcap {i=1}^m s{a_i} \right |$$

二项式反演

二项式反演的式子具体归纳成两个式子：

• $g_n$ 表示至多 $n$ 种的方案数量，$f_n$ 表示恰好 $n$ 种的方案数量。

$$f_n=\sum_{i=0}^{n} (-1)^{n-i} C^i_n g_i \Longleftrightarrow g_n=\sum^n_{i=0} C_n^if_i $$

• $g_k$ 表示至少 $k$ 种的方案数量，$f_k$ 表示恰好 $k$ 种的方案数量。

$$f_k=\sum_{i=k}^{n} (-1)^{i-k} C^i_k g_i \Longleftrightarrow g_n=\sum^n_{i=k} C_k^if_i $$