ARC096E Everything on It 题解

ARC096E Everything on It

题意

• 有一个包含 $n$ 个元素的集合 $S$。
• 你要选择若干个互不相同的 $S$ 的子集，使得每个元素至少出现两次，求方案数。
• $n \le 3 \times 10^3$，答案对 $M$ 取模。

题解

考虑容斥，设 $f(i)$ 表示有至少 $i$ 个数出现了最多一次，则答案为 $\sum_{i=0}^n (-1)^i\binom ni f(i)$。

枚举这 $i$ 个数被划分到 $j$ 个集合中。由于可能有一些数没有出现过，因此我们可以新增一个数 $0$，将这 $i+1$ 个数划分到 $j+1$ 个集合中，与 $0$ 在同一集合的数没有出现过，这部分方案数为 $S_2(i+1, j+1)$。

考虑剩下 $n-i$ 个数，首先存在 $2^{n-i}$ 个集合可选可不选，方案数为 $2^{2^{n-i}}$，然后之前的 $j$ 个中每个集合又可以与这 $2^{n-i}$ 个集合并起来，方案数为 $(2^{n-i})^j$。

因此 $f(i) = \sum_{j=0}^i S_2(i+1,j+1) \cdot 2^{2^{n-i}} \cdot (2^{n-i})^j$，最终的答案可以 $\mathcal O(n^2)$ 计算。

代码

const int N = 3e3 + 7;
int n;
modint s[N][N], ans;

inline modint f(int i) {
	modint w = (modint)2 ^ (n - i), o = 1, ret = 0;
	for (int j = 0; j <= i; j++, o *= w)
		ret += s[i+1][j+1] * o;
	--P, w = (modint)2 ^ (n - i), ++P;
	return ret * ((modint)2 ^ w.x);
}

int main() {
	rd(n, P);
	init(n);
	s[0][0] = 1;
	for (int i = 1; i <= n + 1; i++)
		for (int j = 0; j <= i; j++)
			s[i][j] = (j ? s[i-1][j-1] : 0) + j * s[i-1][j];
	for (int i = 0; i <= n; i++)
		if (i & 1) ans -= binom(n, i) * f(i);
		else ans += binom(n, i) * f(i);
	print(ans);
	return 0;
}