弱连通DAG计数

$n$个点的有编号的弱联通DAG计数

像考虑连通图那样考虑，即答案为所有方案数减去不连通的个数。

则令$f[i]$为$i$个点的答案数,$g[i]$为$i$个点的DAG数。

通过枚举$1$所在的联通块可以得到:$f[i]=g[i]-\sum_{j=1}^{i-1}C(i-1,j-1)*f[j]*g[i-j]$

强连通图计数

$n$个点的有编号的强连通图计数。

考虑不是强连通图的图，那么一定在缩点之后至少有两个点。

所以这启发了我们通过枚举缩点后的点来统计不是强连通图。

在DAG计数中有$f[i]=\sum_{j=1}^{i}(-1)^{j-1}*2^{j*(i-j)}*C(i,j)*f[j]$

现在，这里的点是一些点缩点后的点，不妨称作一个团。

但是我们发现，枚举团是非常复杂的，因为枚举每个点属于哪一个团的时间复杂度非常高。

进而我们可以枚举这j个团是由哪些点组成的，而不考虑其他点的情况。

令$ans[i]$为i个点的答案，$g[i][j]$为$i$个点组成$j$个团的方案数（不同团之间没有边）。

则可以得到$ans[i]=2^{2*C(i,2)}-\sum_{k=1}^{i}\sum_{j=1}^{k}g[k][j]*C(i,k)*(-1)^{j-1}*2^{k*(i-k)}*\sum_{j=1}^{i-k}f[j]+ans[i]$

(末尾的$ans[i]$可以通过不枚举g[n][1]来减掉，但是这么做就很难用多项式优化）

但是我们发现，这个式子的最后一项，即$i-k$个点组成的$j$个团所形成的DAG个数，这一项等价于$2^{2*C(i-k,2)}$，因为对于$i-k$个点任意的有向图，在缩点后形成的团，一定是一个DAG。

所以$ans[i]$可以表示为:

$ans[i]=2^{2*C(i,2)}-\sum_{k=1}^{i}\sum_{j=1}^{k}g[k][j]*C(i,k)*(-1)^{j-1}*2^{k*(i-k)}*2^{2*C(i-k,2)}+ans[i]$

再考虑怎么求$g[i][j]$,一种方法是枚举哪些点在一个团中，再通过$ans[i]$来转移，这样的做法，最终的时间复杂度是$N^3$的。

另一种方法更为巧妙，令$G[i]=\sum_{j=1}^{i}(-1)^{j-1}*g[i][j]$。

考虑j个团对$G[i]$的贡献，即奇正偶负，则通过枚举1所在的团的大小，可以得到$G[i]=ans[i]-\sum_{j=1}^{i-1}C(i-1,j-1)*ans[j]*G[i-j]$。

这样$ans[i]$的式子即为

$ans[i]=2^{2*C(i,2)}-\sum_{k=1}^{i}G[k]*C(i,k)*2^{k*(i-k)}*2^{2*C(i-k,2)}+ans[i]$

令$h[i]=2^{2*C(i,2)}$

然后两边同减掉$ans[i]$，再提出$G[n]$则可以推出:

$G[i]=h[i]-\sum_{j=1}^{i-1}G[j]*h[i-j]*2^{j*(i-j)}*C(i,j)$

又可以推出

$ans[i]=G[i]+\sum_{j=1}^{i-1}ans[j]*G[i-j]*C(i-1,j-1)$

这样，便可以在$N^2$的时间复杂度解决这个问题。