非常厉害的题！看完题解学到了很多。
Description
Solution
不妨先考虑，\(G\) 中不含 A 怎么做。由于图弱连通，因此边数下界为 \(n-1\)。造一条链即可达到该下界，因此答案为 \(n-1\)。
若 \(G\) 中含 A，则有若干对点，被钦定在了同一 SCC 内。假设各个 SCC 的点数依次为 \(s_1,s_2,\cdots,s_k\)，则第 \(i\) 个 SCC 内部有 \(s_i\) 条边（特别的，若 \(s_i=0\) 则其内部没有边）；另外，我们需造一条链，将这些 SCC 连到一起，因此边数为
问题转化为，最小化大小 \(>1\) 的 SCC 数量。
注意到，点集 \(S\) 能成为 SCC，当且仅当 \(\forall x,y \in S\)，\(G_{x,y}\) 不为 X；\(\forall x \in S,y \notin S\)，\(G_{x,y}\) 不为 A。对于第二个条件，我们对所有 \(G_{x,y}\) 为 A 的 \((x,y)\) 连一条边，将各连通块缩成一个点，那么 \(S\) 须有若干个“点”组成。对于第一个条件，我们对所有 \(G_{x,y}\) 为 X 的 \((bel_x,bel_y)\) 连一条边，其中 \(bel\) 表示 \(x\) 所属的“点”；特别的，若 \(bel_x \neq bel_y\)，则无解。那么，\(S\) 必须是独立集。
不难发现，大小 \(=1\) 的点不会参与 SCC 的合并，因此只用考虑大小 \(>1\) 的点，而这样的点只有 \(m=\lfloor \frac n 2 \rfloor \le 23\) 个。于是，问题转化为：给定一个大小 \(\le 23\) 的无向图，求其最少能被划分为多少个独立集。
考虑 \(\text{dp}\)。令 \(f_{c,s}\) 表示，点集 \(s\) 能否能否被划分为 \(c\) 个独立集。转移是平凡的，若存在 \(s\) 的子集 \(t\) 使得 \(g_t=f_{c-1,s-t}=1\)，则 \(f_{c,s}=1\)，其中 \(g_t\) 表示 \(t\) 是否为独立集。于是，我们得到了一个 \(O(3^m m)\) 的做法。
考虑优化。注意到转移可被化为子集卷积的形式，使用占位多项式 + FWT 容易做到 \(O(2^m m^3)\)，依然无法通过。
上述做法都没有很好的运用 \(g\) 的性质：若 \(S\) 为独立集（\(g_S=1\)），则 \(S\) 的所有子集也是独立集（\(\forall T \subseteq S,g_T=1\)）。这意味着，子集卷积与 or 卷积的结果相同。每次求 or 卷积，复杂度是 \(O(2^m m^2)\) 的。
更进一步的，预处理出 \(g\) 作 FMT 的结果，那么对 \(g\) 作 \(k\) 次 FWTor 的第 \(i\) 位集为 \(g_i^k\)。同时，我们需要对于每个 \(k\)，计算其 iFWT 后 \(\{1,2,3,\cdots,m\}\) 处的点值，类似容斥地计算即可。
总时间复杂度 \(O(2^m m)\)，其中 \(m \le 23\)，足以通过本题。
标签：le,bel,卷积,sum,SCC,子集,CF908H From： https://www.cnblogs.com/ducati/p/17145930.html