我们先端上来一个美味的结论。
对于一张有 \(n\) 个点的竞赛图 \(G\),它的 SCC 数量等于:
- 将 \(G\) 的 \(n\) 个点划分为两个点集 \(S\) 和 \(T\),且要求 \(|T|>0\),对于任意的 \(u\in S\) 和 \(v\in T\),\(u\) 和 \(v\) 之间的连边方向为 \(u\to v\) 的方案数。
考虑将图 \(G\) 进行缩点,竞赛图缩点后的形态一定是 \(scc_1\to scc_2\to\ldots\to scc_k\) 这么一条链,同时链上每个点再向后面所有点连边。然后我们任选一个 \(0\le p<k\),将 \(scc_p\) 及它前面的 \(scc\) 内部的点划分到 \(S\),将 \(scc_{p+1}\) 到 \(scc_k\) 内部的点划分到 \(T\),容易发现和上面的方案正好构成双射,且 \(p\) 的取值恰好为 \(k\) 种,也就是 SCC 个数。
ARC163D Sum of SCC
呃,根据上面的结论,直接数划分点集且恰好 \(m\) 条正向边的方案数。
直接设 \(f_{i,j,k}\) 表示当前已经给前 \(i\) 个点划分好了点集,此时 \(|S|=j\),有 \(k\) 条正向边的方案数,转移考虑刷表,讨论 \(i+1\) 号点放到哪个集合:
-
放到 \(S\) 集合中,连到 \(T\) 内的 \(i-j\) 条边全是反向边,连到 \(S\) 内的 \(i\) 条边任意定向,枚举 \(x\) 条边为正向边,有 \(f_{i+1,j+1,k+x}\leftarrow f_{i,j,k}\times\binom{j}{x}\)。
-
放到 \(T\) 集合中,从 \(S\) 内连来的 \(j\) 条边全是正向边,连到 \(T\) 内的 \(i-j\) 条边任意定向,枚举 \(x\) 条边为正向边,有 \(f_{i+1,j,k+j+x}\leftarrow f_{i,j,k}\times\binom{i-j}{x}\)。
时间复杂度 \(O(n^5)\)。
标签:个点,ARC163D,scc,计数,SCC,条边,正向 From: https://www.cnblogs.com/los114514/p/18285341