题解：P10596 BZOJ2839 集合计数

· · 题解

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

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。

仍然是钦定。设 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)