菜王的 blog

nb 题，我想不到的。

首先，SCC 个数显然是一个很强的东西，看起来就显得很不可维护，至少不能高效的表示进状态里。

然后我们考虑把 SCC 个数转化下：

有结论：一个竞赛图的 SCC 个数等于将其点集划分为两个集合 $A, B$（可为空集）并满足以下限制的方案数 $-1$：

• 对于每条满足 $u \in A, v \in b$ 的边 $(u, v)$，都满足其方向为 $u \to v$。

证明这个结论也很简单，考虑将这个图缩点，然后它仍然是一个竞赛图，并且是一个 DAG。考虑它的拓扑序 $p_1, p_2, p_3, \dots, p_k$（因为它是竞赛图，所以拓扑序唯一），并找到一个分界点 $i(0 \le i \le k)$，将 $p_1, p_2, \dots, p_i$ 所对应的 SCC 划入 $A$，将 $p_{i + 1}, p_{i + 2}, \dots, p_k$ 所对应的 SCC 划入 $B$。

可以发现一定只有这样划分才是合法的方案，因为把一个 SCC 分到两个集合，一个集合内拓扑序不连续的情况都是不合法的。而每个 $i$ 就对应了一种合法的方案，且 $i$ 的取值共有 $k + 1$ 种，$-1$ 则变为 $k$，即 SCC 个数。

现在我们的目标就变为对上述划分方案计数，而这个计数是简单的，直接 dp 即可：设 $f_{i, j, k}$ 为加入了 $1 \sim i + j$ 号点，且满足 $|A| = i, |B| = j$，有 $k$ 条满足要求的边的方案数。

考虑将 $i + j + 1$ 号点加入到 $A$ 或 $B$，转移如下：

$f_{i + 1, j, k + x} \gets \binom ixf_{i, j, k} (0 \le x \le i)\\ f_{i, j + 1, k + i + x} \gets \binom jxf_{i, j, k} (0 \le x \le j)\\$

对第一个转移的解释：在 $A$ 内加入最大点 $u$，$u$ 向 $B$ 内的连边都是逆向的，向 $A$ 内的连边任意。钦定 $x$ 条为正向的，则系数为 $\binom ix$。

对第二个转移的解释：在 $B$ 内加入最大点 $u$，$u$ 向 $A$ 内的连边都是正向的，向 $B$ 内的连边任意。钦定 $x$ 条为正向的，则系数为 $\binom jx$。

时间复杂度为 $O(n^3m)$，其中状态数为 $O(n^2m)$，转移为 $O(n)$。

code