题解：P17862 「GLR-R5」霜降 / pruina

· · 题解

出题人题解。放个无聊题来送分，感觉可以做到更好。

令 T=V\setminus S，k=|T|=n-m\leq 4，不妨考虑暴力枚举 T 内部的连边情况。

假设我们知道只考虑 S 内部连边时 S 的一个连通块划分 C_1,C_2,\cdots,C_c。令 A_i 表示对于任意 v\in T，v\in A_i 当且仅当 \exists u\in C_i，边 (u,v) 存在。此时两个连通块 C_i,C_j 若满足 A_i=A_j，它们与其它点的连通情况肯定是一样的，因此本质不同的连通情况只取决于 A_i 组成的集合 \mathcal{A}。

此时如果暴力枚举 \mathcal{A} 和 T 内部的连边情况，就可以检查任意一个 U\subseteq T 是否满足 T 中只保留 U 能否使得 S 连通。这一部分的时间复杂度是 O(k2^{2^k+\binom{k}{2}+k})。问题转变为给定 \mathcal{A}，计算对应的连边方案数 f_{\mathcal{A}}。

连通块划分考虑 EGF，令 F(x)=\sum\limits_{i=1}^{m-1}\frac{x^i}{i!}g_i\sum\limits_{A\in \mathcal{A}}(2^i-1)^{|A|}，其中 g_i 是 i 个点的有标号无向连通图个数。所求即为 m![x^m]\exp(F(x))。但是这样算出来只是钦定 A_i\in \mathcal{A}，所以还需要子集容斥一下得到真正的 f。

使用 O(n^2) 的 exp 时间复杂度为 O(2^{2^k}m^2)，不太能过。但是发现 F(x) 只取决于 \mathcal{A} 中 |A| 形成的多重集，所以本质不同的 F(x) 个数为 t(k)=\prod\limits_{i=1}^k\left(\binom{k}{i}+1\right)。

最后的时间复杂度 O(t(k)m^2+k2^{2^k+\binom{k}{2}+k})，其中 t(4)=350。