图中的一些计数问题

无向连通图

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[j]

那么容斥一下,可以得出:f[i]=\sum_{j=1}^{i}(-1)^{j-1}*2^{j*(i-j)}*C(i,j)*f[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]

但是我们发现,这个式子的最后一项,即i-k个点组成的j个团所形成的DAG个数,这一项等价于2^{2*C(i-k,2)},因为对于n-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)}

再考虑怎么求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]=\sum_{j=1}^{i-1}C(i-1,j-1)*f[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)}

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

对于NlogN的做法,在这个博客中有->链接点这里

 

 

 

参考资料

1.Counting.pdf 来源于UOJ群文件中

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

发表评论

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