CF908H New Year and Boolean Bridges

Genius_Star · 2026-04-25 19:59:34 · 题解

很牛的题啊。

先找一下性质，容易发现：

若 f(u, v) \operatorname{and} f(v, u) = 1，则 f(u, v) = f(v, u) = 1，即两点双向可达，那么 u, v 在一个 SCC 里面。
若 f(u, v) \operatorname{xor} f(v, u) = 1，则等价于 u, v 不在一个 SCC 内且 f(u, v) \operatorname{or} f(v, u) = 1。
若 f(u, v) \operatorname{or} f(v, u) = 1，单独看不太好找性质，但是你发现对于所有 u, v 一定都满足这个条件；即对于任意两个点 u, v，一定存在 u \to v 的路或者 v \to u 的路；这说明，缩点后是一条链，因为若不是链的话出现 A \to B, A \to C 分叉的情况，B, C 之间就不存在路可达了。

那么通过性质，我们容易想想到用并查集将 u, v 一定在一个 SCC 里的点合并起来。

那么现在问题转化为有 m 个点集 S_1, \cdots, S_m，每个点集内的点一定要在同一个 SCC 中，有 q 个形如 u, v 两个集合 S_u, S_v 一定不能并成一个 SCC 的限制，问最小边数。

考虑一个 l 个点的 SCC，显然其边数最少是用一个 l 条边的环将它们串起来；注意若 l = 1，那么不需要边。

于是考虑最后缩点后的链的长度 len（SCC 个数）与点数 = 1 的 SCC 数量 cnt，那么显然最小边数是 n - cnt + len - 1，于是要求 len - cnt 即点数 >1 的 SCC 个数 p 尽可能的少。

对于一个单点集合 S_i = \{x \}，显然其单独成一个 SCC 最优，因为如果找一个单点集合合并成 SCC，那么 >1 的 SCC 个数会增加，找一个 >1 的 SCC 合并不会造成影响。

于是只用考虑 |S_i| > 1 的这些集合，显然这样的集合数量最多是 \frac{n}{2} 个；那么问题转化为，给定 m' 个点，然后有 q' 条边，将这些点划分为若干独立集，使得划分数最小。

容易想到 dp_S 表示将 S 划分的最多独立集个数，令 f_S 表示 S 是否是独立集，那么有转移：

dp_S = \min_{T \subsetneqq S, f_T = 1} dp_{S - T} + 1

直接做是 O(3^{\frac{n}{2}}) 无法通过；考虑怎么优化一下？

考虑不直接这样做，因为答案最多是 n，所以可以一层一层做；具体的，初始令 g_i 表示 S 是否是独立集合，f \gets g；然后每次拓展一层，相当于进行一次子集卷积：

f'_S = \sum_{S' \cap T' = \emptyset, S' \cup T' = S} f_{S'} g_{T'}

设当前拓展了 p 轮（初始 p = 1），这样 f'_S 就是存的是将 S' 划分为 p 轮的方案数。

那么这样每次拓展做一次子集卷积，如果此时 f_{2^{m'} - 1} 非 0，那么说明这些点最少只能划分成 p 个独立集，直接 FWT 是 O(2^{\frac{n}{2}} n^3) 的，依然无法通过。

考虑实际上可以当作 \operatorname{or} 卷积，而非子集卷积：

f'_S = \sum_{S' \cup T' = S} f_{S'} g_{T'}

因为若这样算既然有贡献，那么把它们的交从 T' 中去掉依然是一个独立集，是一定会造成贡献的。

于是可以当作 \operatorname{or} 卷积的 FWT 做，即：

FWT(f') = FWT(f) \cdot FWT(g)

提前算出 FWT(g)，那么每次点乘即可算出 FWT(f')；但是我们需要判断 IFWT(FWT(f'))_{2^{m'} - 1} > 0，如果每次算都 IFWT 算一遍的话时间复杂度是 O(2^{\frac{n}{2}} n^2) 的，实现不好依旧无法通过。

实际上你只需要 2^{m'} - 1 这一位的值，因为 FWT 是线性变换，所以你可以提前预处理其它项对 2^{m'} - 1 的贡献系数或者直接反演：

IFWT(FWT(f'))_{2^{m' - 1}} = \sum_{S} (-1)^{n - |S|} FWT(f')_S

于是最终复杂度是 O(2^{\frac{n}{2}} n)，可以轻松通过。