自动搬运

查看原文

来自洛谷，原作者为

	2huk Where should my destinaion be at? 我问我自己。

搬运于2025-08-24 22:59:30，当前版本为作者最后更新于2024-06-29 11:41:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

选自 容斥原理 & 二项式反演。

2 二项式反演

2.1 反演

对于两个数列 $g(x), f(x)$ 而言，若它们之间存在某种对应关系，使得不仅能从 $f(x)$ 推出 $g(x)$，还能从 $g(x)$ 反推出 $f(x)$，那么这个反推的过程就叫做反演。

形象化地，若原数列为 $g(n)$，新数列为 $f(n)$，且满足 $f(n) = \sum\limits_{i=0}^n a_{n, i} \times g(i)$，那么反演就是我们通过 $f(n)$ 得到 $g(n)$，即 $g(n) = \sum\limits_{i=0}^n b_{n, i} \times f(i)$，那么我们可以这样表示：

$$f(n) = \sum\limits_{i=0}^x a_{n, i} \times g(i) \Longleftrightarrow g(n) = \sum\limits_{i=0}^n b_{n, i} \times f(i) $$

事实上，通过 $g(x)$ 反推回 $f(x)$ 可以用 $\Theta(n^3)$ 的复杂度解 $n$ 元一次方程组。但是在一些特殊的对应关系例，反演会化出一些优美的形式，例如莫比乌斯反演，单位根反演，子集反演，二项式反演等。

2.2 容斥原理与二项式反演

全集 $U = \{S_1, S_2, \dots, S_n\}$ 且满足任意 $i$ 个集合的并集、交集的大小都相同。

设 $f(n)$ 表示 $n$ 个集合的交集的大小，$g(n)$ 表示 $n$ 个集合的补集的交集的大小，有：

$$g(n) = \left|\bigcap_{i=1}^n S_i\right| = |U| - \left|\bigcup_{i=1}^n \overline{S_i}\right| = \left|U\right| + \sum_{i=0}^n (-1)^i \sum_{1 \le a_1 < \dots < a_i \le n }\left|\bigcap_{j=1}^i \overline{S_{a_j}} \right| = \sum_{i=0}^n (-1)^i\dbinom ni f(i) $$

以及：

$$f(n) = \left|\bigcap_{i=1}^n \overline{S_i}\right| = |U| - \left|\bigcup_{i=1}^n S_i\right| = \left|U\right| + \sum_{i=0}^n (-1)^i \sum_{1 \le a_1 < \dots < a_i \le n }\left|\bigcap_{j=1}^i S_{a_j} \right| = \sum_{i=0}^n (-1)^i\dbinom ni g(i) $$

可得：

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

2.3 形式

• 形式一：

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

• 形式二：

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

实际上这个式子中的 $f(i)$ 等于形式一中的 $(-1)^if(i)$，代入即可。

• 形式三：

$$g(n) = \sum_{i=n}^N \dbinom Ni f(i) \Longleftrightarrow f(n) = \sum_{i=n}^N (-1)^{N - i}\dbinom Ni g(i) $$

这个式子是「至多」和恰好的转化。

• 形式四：

$$g(n) = \sum_{i=n}^N \dbinom in f(i) \Longleftrightarrow f(n) = \sum_{i=n}^N(-1)^{i - n} \dbinom in g(i) $$

这个式子是「至少」和恰好的转化。

注意：这里的「至少」与「至多」的概念并不是朴素的：

1. 「至少」：钦定了 $i$ 个性质，剩下的性质不作限制。
2. 「至多」：钦定了 $i$ 个性质不作限制，剩下的必须满足性质。

---

2.4.2 集合计数$^{\text{BZOJ 2839}}$

• 给定 $n, k$。令 $S_0 = \{1, 2, 3, \dots, n\},S_1 = \{S \mid S \subseteq S_0\}$，求有多少 $S_1$ 的子集 $S$ 满足 $\left|\bigcap\limits_{S \in S_1} S\right| = k$。
• $k \le n \le 10^6$。

仍然是钦定。设 $f(k)$ 表示「至少」$k$ 个元素是集合的交集，即钦定 $k$ 个元素作为集合的交集，剩余不做限制的方案数，会有重复。有：

$$f(k) = \dbinom nk \left(2^{2^{n-k}}-1\right)$$

设 $g(k)$ 表示恰好 $k$ 个元素是集合的交集的方案数，有：

$$f(k) = \sum_{i=k}^n \dbinom ik g(i)$$

二项式反演得：

$$g(k) = \sum_{i=k}^n(-1)^{i-k} \dbinom ik f(i) = \sum_{i=k}^n(-1)^{i-k} \dbinom ik \dbinom ni \left(2^{2^{n-i}}-1\right) $$

$g(k)$ 即为所求。时间复杂度 $\Theta(n)$。