题解：AT_abc450_f [ABC450F] Strongly Connected 2

· · 题解

简述题意

给你一个有 n + m - 1 条边的有向图，其中有 n - 1 条是 (i, i - 1)(2 \le i \le n)，其余 m 条会给出，且满足这 m 条边中的 (u_i, v_i)，有 u_i < v_i，问删去 m 条边的 2^m 中选法中，有多少满足删后的图是强连通的，答案对 998244353 取模。

解题思路

由于存在一条从 n 到 1 的链，图强连通只需满足存在一条路径，从 1 出发可以到达 n，题目就转化为了求有多少边集满足能从 1 走到 n。

假设当前选的边可以覆盖点 [1, k]（覆盖可以理解为这些点强连通），若新加的一条边 (u, v)，若满足 u \le k 和 v > k，则加入这条边后的覆盖范围变为 [1, v]，证明是显然的，不多赘述。

考虑 dp，设 dp_i 表示只考虑 v \le i 的边，能覆盖 [1, i] 的方案数，记 cnt_i 为 v \le i 的总边数，R_{i, j} 为 u > i, v \le j 的边数，可以得到转移

dp_i = 2 ^ {cnt_i} - \sum_{j = 1}^{i - 1}{dp_j \times 2 ^ {R_{j, i}}}

我们再记 L_{i, j} 表示 u \le i, v \le j 的边数，不难发现

R_{i, j} = \frac{L_{i, j}}{2 ^ {cnt_j}}

于是原式子可写为

dp_i = 2 ^ {cnt_i} \left(1 - \sum_{j = 1}^{i - 1}{\frac{dp_j}{2 ^ {L_{j, i}}}} \right)

答案为 dp_n ，时间复杂度 O(n^2) ，考虑优化。

发现 L_{i,j} 是 L_{i, j - 1} 加上 v = j, u \le i 的边数，记 S = \sum_{j = 1}^{i - 1}{\frac{dp_j}{2 ^ {L_{j, i}}}}，假设已知上一个 S，对于每条 v = i 的边，我们只需把 j \ge u 的项乘上 \frac{1}{2} 即可更新贡献，计算 dp_i 后再将 dp_i 计入贡献。区间乘、单点加、求区间和，可以用线段树维护。

具体实现，先便利 v = i 的每条边，对区间 [u, i - 1] \times \frac{1}2 ，然后查询 [1, i - 1] 计算 dp_i，再加入 dp_i 值到点 i 即可。

由于每条边只会遍历一次，所以时间复杂度为 O(n \log n)。