[ARC163D] Sum of SCC

神秘 trick 题。

根本想不到的 Trick：一个竞赛图的强连通分量的个数等价于：

把整个图分成两个集合 \(S,T\)， \(u\in S,v\in T\),满足所有边的方向为 \(u\to v\)。

为什么是对的呢？考虑到把整个图缩点以后就是一个 DAG，而且还是一个竞赛图，然后竞赛图的拓扑序是唯一的，找到一个拓补序的分界点，我们把它割断成两个子集，那么前半部分的都是指向后面的。容易发现，这是唯一合法的方案。最后要减去空集的情况。

问题转化成：将 \(n\) 个点，分成两个集合，两个集合之间的边是单向的，小指大只有 \(m\) 条边。

考虑刷表 dp。

定义状态 \(f_{i,j,k}\) ，集合 \(S\) 有 \(i\) 个点，集合 \(T\) 有 \(j\) 个点，有 \(k\) 条边是小点指向大点。
现在与 \(f_{i-1}\) 就是多了 \(i-1\) 条新边，考虑转移。

• \(1.\) 把 \(i\) 扔进 \(S\)。
  此时，\(i\to T\) 的边的固定方向的，是大指小，枚举有多少条边是指向自己的就行。
  转移方程式为：
  \(f_{i,j,k}=\sum\limits_{l=0}^{i-1} f_{i-1,j,k-l}\times C_{i-1}^l\)

• \(2.\) 把 \(i\) 扔进 \(T\)。
  仍然枚举边数量。
  \(f_{i,j,k}=\sum\limits_{l=0}^{j-1} f_{i,j-1,k-i-l}\times C_{j-1}^l\)

然后转移 \(O(n)\)，总状态为 \(O(n^2m)\)，时间复杂度 \(O(n^5)\)。

整个题难点在第一步