发现这个竞赛图一定能被分为两个集合 \(A\)，\(B\)。满足 \(\forall u\in A,v\in B\)，均有 \(u\to v\in E\)。答案就是划分这两个集合的方案数。
证明：
首先，竞赛图缩完点后一定是一条链，对强连通分量进行标号，满足编号小的强连通分量指向编号大的强连通分量。不妨令竞赛图 \(G\) 缩完点后的强连通分量编号分别为 \(a_1,a_2\dots a_k\)。则这个图 \(G\) 存在 \(k\) 个 \(i\) 能分出两个满足条件的集合，即 \(\{a_1\dots a_i\}\) 和 \(\{a_{i+1}\dots a_k\},i\in[1,k]\)。而分出的 \(k\) 种集合 \(A\)，\(B\) 是与其形成双射关系的，故可转化。
这时就很好用动态规划求解了，定义 \(f_{i,j,k}\) 表示 \(i\) 个点的竞赛图中，\(A\) 集合有 \(j\) 个点，有 \(k\) 条边满足 \(u<v\) 的方案数。
采用刷表法，考虑转移。
若第 \(i+1\) 个点在 \(A\) 中，内部有 \(c\) 条边连向 \(i+1(c\le j)\)，则对 \(f_{i+1,j+1,k+c}\) 产生贡献。
若第 \(i+1\) 个点在 \(B\) 中，内部有 \(c\) 条边连向 \(i+1(c\le i-j)\)，则对 \(f_{i+1,j,k+j+c}\) 产生贡献。
可得到方程：
\(f_{i+1,j+1,k+c}\leftarrow f_{i+1,j+1,k+c}+f_{i,j,k}\times\dbinom{j}{c}\)
\(f_{i+1,j,k+j+c}\leftarrow f_{i+1,j+1,k+j+c}+f_{i,j,k}\times\dbinom{i-j}{c}\)
答案容易得到：\(\sum\limits_{i=0}^{n-1} f_{n,i,m}\)。
时间复杂度：\(\mathcal{O}(n^5)\)。
空间复杂度：\(\mathcal{O}(n^4)\)。
标签：dots,连通,竞赛,个点,ARC163D,题解,Sum,条边,集合 From： https://www.cnblogs.com/Pengzt/p/17771315.html