一道图论计数好题:《两弹一星》

发布于 2018-04-30  4.6k 次阅读


题意:定义一个简单无向图的权值为无环的联通块数x的m次方,求由n个点构成的有标号图的权值之和,n<=3e4,m<=20。

直接来说正解,先考虑每个图对答案的贡献:

$$x^m = \sum _{i=0} ^{m} S(m,i) \, i! \; C_{x}^{i}$$

由于m比较小,我们可以直接枚举i,然后对于不同的x,求和的前两项是确定的,问题转化为求最后一项的和。

这里组合数的意义就是,假定我有一个图,它的树联通块数为x,那么对于一个i,它的贡献就是从中任选出i个块的方案数。那么我们转化一下,如果我们确定了树的联通块大小,那么它的贡献就是剩下的点随便连边的方案数,因此我们有了一个做法,设f[i][j]表示i个点的带标号无向图,所有i个点构成了j个树联通块的方案数;g[i]表示i个点的生成树个数,就有如下转移:

$$f[i][j]=\sum _{k=1} ^{i} f[i-k][j-1] * g[k] *C_{i-1} ^{k-1}$$

显然这个式子可以O(n^3)计算,如果我们用FFT优化,只计算j<=m的部分,就可以做到O(mnlogn)的复杂度。

 

题面(虽然没卵用):

本文隐藏内容 登陆 后才可以浏览


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974