图中的一些计数问题

无向连通图

$n$个点的有编号的无向连通图计数

令$f[i]$表示$i$个点的答案,不妨考虑总数减去不连通的个数。

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

即考虑$1$所在的联通块的大小。

这个式子还可以通过分治FFT优化。

 

DAG计数

$n$个点的有编号的DAG计数

令$f[i]$表示$i$个点的答案,则考虑枚举哪些是入度为$0$的点。

但是直接统计不好统计,但是可以算出至少有$j$个点入度为$0$的点的方案数,即为$2^{j*(i-j)}*C(i,j)*f[i-j]$。

那么容斥一下,可以得出:$f[i]=\sum_{j=1}^{i}(-1)^{j-1}*2^{j*(i-j)}*C(i,j)*f[i-j]$。

可以发现,在这个容斥中,对于入度为$0$的点恰好有$j$个的方案被统计了$\sum_{k=1}^{j}(-1)^{k-1}*C(j,k)=-\sum_{k=0}^{j}(-1)^k*C(j,k)+C(j,0)=-[j==0]+1$,所以这个容斥将每个恰好有$j$个入度为$0$的点的方案正好都统计了一遍。

同时,这个式子也可以通过分治FFT优化。

 

弱连通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$的时间复杂度解决这个问题。

对于$NlogN$的做法,用多项式技巧即可。

 

参考资料

http://blog.leanote.com/post/rockdu/0245

发表评论

电子邮件地址不会被公开。 必填项已用*标注