「Codeforces914D」Stranger Trees-矩阵树定理+拉格朗日插值

发布于 2018-10-05  152 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:「Codeforces914D」Stranger Trees-矩阵树定理+拉格朗日插值

Description

给定一棵有\(n\)个节点的无权无向树。

求对于这\(n\)个点,以及每个\(k=0,1,2...n-1\),有多少棵由这\(n\)个点之间的边构造成的树,与给定的树恰好有k条边重复。

答案\(mod 10^9+7\)输出。

\(n \leqslant 100\)

Solution

考虑矩阵树定理求出的每棵生成树边权(重边条数定义为边权)的乘积的和。

设出现在给定的树的边的边权定义为\(x\),那么答案就是\(\sum_{i=0}{n-1} x^i ansi\),其中\(ans_i\)表示与给定的树有\(i\)条重边的生成树个数,即答案。

发现当\(x\)确定时,这个多项式可以用矩阵树定理求出。所以把\(x=1..n\)带入多项式,用拉格朗日插值法求出\(ans_i\)即可。

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:「Codeforces914D」Stranger Trees-矩阵树定理+拉格朗日插值


或许前方只有...伸手不见五指的夜路,即使如此,我还是要充满信心、继续向前, 相信星星的光芒...多少会照亮前方的道路,走吧!我们踏上旅程吧!