容斥原理 & 二项式反演

2huk · 2024-04-30 15:53:02 · 算法·理论

0 集合

考虑「集合」和「限制」的联系。

对于某个限制 P_i，令满足这个限制的方案组成的集合为 S_i，那么一些集合中的定义：

1 容斥原理

1.1 基础

1.1.1 「集合的并」\to「集合的交」

我们有：

即：

证明见 OI-Wiki。

这样我们就可以将「集合的并」转化成「集合的交」，也即将「逻辑或」转化成「逻辑与」。

1.1.2 「集合的交」\to「补集的并」

我们有：

即集合的交的大小，等于全集的大小减去每个集合的补集的交的大小。

当然，我们也可以通过 Part.0 理解，即「满足所有条件的方案数」等于「总方案数」减去「至少一个条件不满足的方案数」。

这样我们就可以将「集合的交」转化成「补集的并」，也即将「逻辑与」转化成「逻辑或」。

1.1.3 「集合的并」\to「补集的交」

类似的，我们有：

即集合的交的大小，等于全集的大小减去每个集合的补集的并的大小。

当然，我们也可以通过 Part.0 理解，即「至少满足一个条件的方案数」等于「总方案数」减去「所有条件都不满足的方案数」。

这样我们就可以将「集合的并」转化成「补集的交」，也即将「逻辑或」转化成「逻辑与」。

1.2 例题

1.2.1 不定方程非负整数解计数

• 给定 n, m, b_i，求关于 x_i 的不定方程 \sum_{i=1}^n x_i = m 的满足 x_i \in [0, b_i] \cap \mathbb{N} 的解的数量。

显然一共有 n 个条件，第 i 个条件 P_i 为 0 \le x_i \le b_i。题意要求这 n 个条件都要满足，也就是要求 \left| \bigcap\limits_{i=1}^n S_i\right|。

发现这个条件的上界 x_i \le b_i 是极难处理的，但是下界 x_i \ge 0 的处理是容易的，因此我们考虑 Part.1.1.3 的方法。

对于 |U| 的计算，即总方案数的计算，是可以用组合数学解决的。显然这是基础的插板法，答案为 \dbinom {n+m-1}{n-1}。具体见 OI-Wiki。

发现后半部分貌似也不能直接求解。观察形式是集合并，考虑用 Part.1.1.2 的方法。

我们可以 dfs 枚举上式中的 a_1, a_2, \dots, a_i，计算出答案后乘上系数 (-1)^i 并累加即可。此时需要解决的是 \left|\bigcap\limits_{j=1}^i \overline{S_{a_j}} \right|，即所有 P_{a_j} 限制都不满足的方案数。

考虑 P_{a_j} 限制不满足的本质，是不满足 0 \le x_{a_j} \le b_{a_j}，即 x_{a_j} \ge b_{a_j} + 1。完成这件事情是极易的。由于题目要求 \sum_{i=1}^n x_i = m 且我们要求所有 x_{a_j} \ge b_{a_j} +1 。那么我们可以将 m 减去 b_{a_j} + 1 的和，然后将限制转化成 x_{a_j} \ge 0。这样就又转化成了前面的插板法。

总时间复杂度 \Theta(2^nn)，组合数计算不计。

1.2.2 [HAOI2008] 硬币购物^{\text{Luogu P1540}}

• 共有 4 种硬币。面值分别为 c_1,c_2,c_3,c_4。某人去商店买东西，去了 n 次，对于每次购买，他带了 d_i 枚 i 种硬币，想购买 s 的价值的东西。请问每次有多少种付款方法。

若我们分别购买了四种商品 x_1, x_2, x_3, x_4 件，那么需要满足的条件为 0 \le x_i \le d_i。

发现这个上界是做不了的，但是下界的处理是极易的。我们思考这些问题：

1. 求满足 x_i \ge 0（也就是无限制）时，凑成 s 的方案数。

显然是完全背包。预处理即可。

2. 求满足 x_i \ge d_i（d_i 给定）时，凑成 s 的方案数。

既然至少要买 d_i 件，那么我们先将这 d_i 件买上，即 s \gets s - \sum c_id_i。然后就是第一个问题了。

3. 求满足 0 \le x_i \le d_i（d_i 给定）时，凑成 s 的方案数。即本题。

容斥。我们有公式：

即「n 个条件都满足的方案数」等于「总方案数」减去「至少一个条件不满足的方案数」。

在本题中，「n 个条件都满足的方案数」即 \forall i, 0 \le x_i \le d_i，「至少一个条件不满足的方案数」即 \exist i, x_i \ge d_i + 1。

那么我们用 2^4 的复杂度枚举哪些条件是不满足的，即哪些 i 需要满足 x_i \ge d_i + 1。然后转化成了问题二。乘上容斥系数累加答案即可。

1.2.3 错排问题

• 求有多少 1 \sim n 的排列 a 满足 \forall i \in [1, n], a_i \ne i。

与 Part.1.2.1 极其相似。仍然是 n 个限制，第 i 个限制 P_i 是 a_i \ne i。仍然考虑式子：

显然 |U| = n!。后面部分仍然用式子：

显然在排列中每个数的地位都是对称的，所以我们不必以 2^n 的复杂度枚举 a_j，而是指枚举 a_j 的数量 i 即可。

具体地，此时我们的限制是「存在至少 i 个位置 j 满足 a_j \ne j」。那么我们可以先钦定这 i 个位置不动，对于剩下的 n - i 个位置用全排列计算，即这个限制的条件下方案数为 \dbinom ni \times (n - i)! = \dfrac{n!}{i!}。

一步步代回原式，答案为：

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)，那么我们可以这样表示：

事实上，通过 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 个集合的补集的交集的大小，有：

以及：

可得：

2.3 形式

• 形式一：

• 形式二：

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

• 形式三：

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

• 形式四：

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

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

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

2.4 例题

2.4.1 已经没有什么好害怕的了^{\text{Luogu P4859}}

省去某些不重要的步骤后的简化题意：

• 给定两个长度为 n 的升序排序的数组 a_1 \dots a_n, b_1 \dots b_n 和 k。求有多少 1 \sim n 的排列 P 使得存在恰好 k 个位置 j 满足 a_j > b_{P_j}。

首先 DP。设 h(i,j ) 表示 1 \sim i 中恰好有 j 个 k 满足 a_k > b_{P_k}。定义 r(i) = \max \{j \mid b_j < a_i\}，即比 a_i 小的最后一个 b 中的位置。转移考虑位置 i 是否属于 j 个 k 中，即：

设 g(k) 表示「至少」k 个 i 满足 a_i > b_{P_i}，即钦定了 k 个位置 i 使得 a_i > b_{P_i}，而且剩余的位置不做限制的方案数。显然这样计数是会有重复的。可得：

考虑如何解决重复的问题。再设 f(k) 表示恰好 k 个 i 满足 a_i > b_{P_i} 的方案数。显然 f(i) 在 g(k) 中重复计算了 \dbinom ik 次（因为一共有这么多种钦定方案），即：

二项式反演得：