容易发现每年都在考这玩意。每年都不会。
AT_abc213_g [ABC213G] Connectivity 2
显然删边可以变成保留边。
定义状态函数 \(f_s\) 表示保留边，使得 \(s\) 中的点联通的方案数。那么对于 \(k=k0\) 来说，答案应该就是 \(\sum f_{s}[1 \in s \land k \in s]\times g_{U /s}\)。其中 \(g_s\) 为在任意保留 \((u,v) [u \in s \land v \in s]\) 中的边的方案数。
\(g_s\) 是好求的。时间复杂度 \(O(2^n n^2)\)。
\(f_s\) 有：\(f_s=\sum\limits_{\min(s') \subseteq t \subseteq s'}^{} f_{t}\times f_{s/t} \times h(s,t)\)。其中 \(h(s,t)\) 为至少保留一条 \((u,v) [u \in s \land v\in t]\) 的方案数。
这里以 \(\operatorname{lowbit}(s)\) 作为 \(s\) 的代表元，有 \(\min(s)=\operatorname{lowbit}(s)\)。代表元的作用是为了不让相同集合被计算多次，需要满足同种局面代表元唯一。
\(h(s,t)=2^{e(s|t)-e(s)-e(t)}-1\)。时间复杂度 \(O(3^n)\)。
发现对于 \((1,2),(2,3),(1,3)\) 会算重。
原因是这个代表元并不能唯一表示局面。在 \(s=\{1,2,3\}\) 时，可以 \(\{1\},\{2,3\}\)，也可以 \(\{1,2\},\{3\}\)。如何？考虑容斥。因为在钦定一个集合 \(t\) 联通时，就可以统一了。因为 \(s\) 在不联通的时候一定由：\(t_1,t_2,\dots ,t_m\) 合起来。那么枚举包含 \(\min(s)\) 的集合，其它的就可以通过 \(2^{e(s/t)}\) 求得。
转移方程：\(f_s=2^{e(s)}-\sum\limits_{\min(s)\subseteq t \subset s}^{} f_t\times 2^{e(s/t)}\)。时间复杂度 \(O(3^n)\)。