「ARC 096E」Everything On It（容斥原理）

题目大意

「ARC 096E」Everything On It

求有多少个子集族，满足：

• 其中的每个子集都是 $[n]$ 的一个子集；
• 任意两个子集互不相同；
• $1, 2, \cdots, n$ 都在其中出现了至少两次。

答案对素数 $m$ 取模。

数据范围：$n \le 3000, 10^8 \le m \le 10^9 + 9$。

思路分析

我们考虑容斥，枚举出现了不超过一次的数的个数 $i$，这样答案就是 $\sum_{i = 0}^{n} (-1)^i \binom{n}{i} A_i$。

对于某个 $i$，我们不妨假定出现次数不超过一次的数是 $1, 2, \cdots, i$。考虑继续枚举包含 $[1, i]$ 中数的子集个数 $j$。对于除了这 $j$ 个集合以外的集合，它们都不包含前 $i$ 个数，所以方案数是 $2^{2^{n - i}}$。而对于这 $j$ 个集合，发现它们必定两两不同。它们的后 $n - i$ 位共有 $(2^{n - i})^j$ 种可能的取值，而前 $i$ 位每一位都出现了不超过 $1$ 次。这相当于从前 $i$ 个数中选出 $k$ 个数钦定它们没有出现，然后把剩下 $i - k$ 个数分给 $j$ 个集合（第二类斯特林数）。这样，我们已经可以得到答案的式子：

$$\sum_{i=0}^{n} (-1)^i \binom{n}{i} \sum_{j = 0}^{i} 2^{2^{n - i}} \cdot (2^{n - i})^j \sum_{k = 0}^{i} \binom{i}{k} \begin{Bmatrix} i - k \\ j \end{Bmatrix}$$

直接计算的时间复杂度是 $O(n^3)$，不能通过。我们考虑把枚举 $k$ 变为直接计算某个式子。发现下面的等式始终成立：

$$\sum_{i = 0}^{n} \binom{n}{i} \begin{Bmatrix} n - i \\ k \end{Bmatrix} = \begin{Bmatrix} n + 1 \\ k + 1 \end{Bmatrix}$$

考虑该等式的组合意义：左边是将 $n$ 个不同的小球选一些出来，然后划成 $k$ 个集合；右边是将 $n + 1$ 个小球划成 $k + 1$ 个集合。我们把第 $n + 1$ 个小球看作特殊小球，它被划分到的集合中的所有球都会被扔掉，这样两边的组合意义就相同了，我们就证明了这个等式。

于是原式可以简化为：

$$\sum_{i=0}^{n} (-1)^i \binom{n}{i} \sum_{j = 0}^{i} 2^{2^{n - i}} \cdot (2^{n - i})^j\begin{Bmatrix} i + 1 \\ j + 1 \end{Bmatrix}$$

枚举 $i, j$ 直接计算即可，时间复杂度 $O(n^2)$。

代码实现

#include <bits/stdc++.h>