前置知识：求数列幂和
给定数列 \(\{a_n\}\)，对 \(0\leqslant t \leqslant k\)，求 \(\sum\limits_{i=1}^na_i^t\)，\(n,t\leqslant 10^5\)。
我们写出幂次和对应的生成函数 \(F(x)\) \[ \begin{aligned} F(x)=&\sum\limits_{t=0}\left(\sum\limits_{i=1}^na_i^t\right)x^t\\ =&\sum\limits_{i=1}^n\sum\limits_{t=0}a_i^tx^t\\ =&\sum\limits_{i=1}^n\frac{1}{1-a_ix} \end{aligned} \] 然后我们考虑 \(G(x)=\sum\limits_{i=1}^n\left(\ln(1-a_ix)\right)'\)，化简则有 \[ \begin{aligned} G(x)=&\sum\limits_{i=1}^n\left(\ln(1-a_ix)\right)'\\ =&-\sum\limits_{i=1}^n\frac{a_i}{1-a_ix}\\ =&-\sum\limits_{t=0}\sum\limits_{i=1}^na_i^{t+1}x^t \end{aligned} \] 如果我们能求得 \(G(x)\)，则很好就能求出 \(F(x)\)。同时发现 \[ \begin{aligned} G(x)=&\sum\limits_{i=1}^n\left(\ln(1-a_ix)\right)'\\ =&\left(\sum\limits_{i=1}^n\ln(1-a_ix)\right)'\\ =&\left(\ln(\prod\limits_{i=1}^n(1-a_ix))\right)' \end{aligned} \] \(\prod\limits_{i=1}^n(1-a_ix)\) 可以通过分治+NTT 计算，然后求个 \(\ln\) 再求导就好了。复杂度 \(O(n\log^2n)\)。
然后我们考虑这道题。
显然，我们可以把每一个连通块看成一个点，然后只需要考虑连通块的连接方式，每连接一条边额外乘上连通块大小即可。
我们考虑枚举 prufer 序列，如果一个数在 prufer 序列中出现了 \(d\) 次，则其的度数为 \(d+1\)。
那么我们考虑枚举每个点在 prufer 序列中出现的次数 \(d_i\)，则我们有 \[ \begin{aligned} ans=&\sum\limits_{\sum d=n-2}(n-2)!\left(\prod_{i=1}^n(d_i+1)^m\right)\left(\sum_{i=1}^n(d_i+1)^m\right)\left(\prod_{i=1}^n\frac{a_i^{d_i+1}}{d_i!}\right)\\ =&(n-2)!\prod_{i=1}^na_i\sum\limits_{\sum d=n-2}\left(\prod_{i=1}^n\frac{a_i^{d_i}}{d_i!}(d_i+1)^m\right)\left(\sum_{i=1}^n(d_i+1)^m\right) \end{aligned} \] 前面两项是定值，我们先不管。我们考虑后面那个东西，它等价于 \[ \sum\limits_{\sum d=n-2}\sum\limits_{i=1}^n\frac{a_i^{d_i}}{d_i!}(d_i+1)^{2m}\prod\limits_{j\not=i}\frac{a_j^{d_j}}{d_j!}(d_j+1)^m \] 我们考虑构造两个多项式 \(A(x)=\sum\limits_{i}\dfrac{(i+1)^{2m}x^i}{i!},B(x)=\sum\limits_{i}\dfrac{(i+1)^mx^i}{i!}\)，设答案关于 \(\sum d\) 的生成函数为 \(F(x)\)，则有 \[ \begin{aligned} F(x)&=\sum\limits_{i=1}^nA(a_ix)\prod\limits_{j\not=i}B(a_jx)\\ &=\sum\limits_{i=1}^n\frac{A(a_ix)}{B(a_ix)}\prod_{j=1}^n B(a_jx)\\ &=\sum\limits_{i=1}^n\frac{A(a_ix)}{B(a_ix)}\exp\left(\sum\limits_{j=1}^n\ln(B(a_jx))\right) \end{aligned} \] 如果我们求出了 \(\dfrac{A(x)}{B(x)}\) 与 \(\ln(B(x))\)，我们只需要每一项的系数乘上 \(\sum\limits_{i=1}^na_i^t\) 即可。
代码：
1 |
|