题解 P3790 【文艺数学题】

will7101 · 2017-05-30 22:53:09 · 题解

一句话题意

求无向图的所有生成树的权值gcd之和。

暴力枚举边的集合，判断是否是生成树，计算gcd并求和。

复杂度O(N logW 2^M)

在20分做法的基础上加一些剪枝，或者用dfs来枚举生成树。

因为值域不大，考虑枚举gcd的值并进行容斥（反演）。

推式子：

设f(n)=权值gcd为n的生成树个数，我们发现f(n)不是很好直接计算。

于是设F(n)=权值gcd被n整除的生成树个数，

显而易见，F(n)=\sum_{n|d} f(d)。

而且F(n)比较容易得到（可以通过矩阵树定理在O(N^3)的时间内计算）。

进行莫比乌斯反演，得到f(n)=\sum_{n|d} \mu(\frac{d}{n})F(d)

于是

ans=\sum_{n=1}^W {n f(n)}

=\sum_{n=1}^W {n \sum_{n|d} {\mu(\frac{d}{n})F(d)}}

=\sum_{d=1}^W {F(d) \sum_{n|d} {n \mu(\frac{d}{n})}}

=\sum_{d=1}^W {F(d) \phi(d)}

枚举d从1到W，然后加入d整除权值的边，使用矩阵树定理计算F，注意判断生成树个数为0的情况（图不联通）。

复杂度O(W(M+N^3))

注意到生成树都是一条链，不需要使用矩阵树定理，直接利用乘法原理计算。

复杂度O(WM)

在50分做法的基础上进一步优化：

注意到很多时候生成数个数为0（图不联通），一个显然的充分条件是满足条件的边数<N-1，所以我们可以预先筛掉这些情况。

对于每一条边，只会对它权值的因数d造成影响，然后统计每个数作为因数出现了多少次，小于N-1的不用计算。

对于小于\sqrt{W}的因子，它们每个最多出现一次；对于超过\sqrt{W}的因子，由于边权不超过W，每个边权至多只有一个大因子。所以有效的因子总数最多为\sqrt{W}+\frac{M}{N-1}，约为2000。

复杂度O((\sqrt{W}+\frac{M}{N-1})(M+N^3))。