Description
有一个图有\(n\)个树形连通块，第\(i\)个有\(a_i\)个点。你需要再连\(n - 1\)条边使得这个图变成一个树。
对于一个方案\(T\)，我们记\(d_i\)表示第\(i\)个连通块向外连了多少边。那么我们称其价值为： \[ \mathrm{val}(T) = (\sum_{i = 1}^n d_i^m)(\prod_{i = 1}^n d_i^m) \] 其中\(m\)为给定常数。求所有可能的树的价值之和。
\(n\leq 30000, m\leq 30, a_i\in Z_{998244353}\)。
Solution
辣鸡卡常题毁我青春.jpg
先化简一下式子： \[
\begin{aligned}
\quad&\sum_{T} (\sum_{i = 1}^nd_i^m)(\prod_{i = 1}^nd_i^m)\\
=&\sum_{T}\sum_{i = 1}^n d_i^{2m}\prod_{j\neq i} d_i^m
\end{aligned}
\] 观察到度数对答案的贡献一点，很容易想到Prufer序列。我们知道如果一个点度数为\(d_i\)，那么他在Prufer序列中也会出现\(d_i - 1\)次。因此这个问题转化成了一个排列问题……事指数型生成函数的用武之地。
那么我们很容易想到定义两类生成函数： \[ \begin{aligned} A_i(x) &= \sum_{k = 0}^{+\infty}\frac{(k + 1)^{2m}A_i^{k + 1}x^k}{k!}\\ B_i(x) &= \sum_{k = 0}^{+\infty}\frac{(k + 1)^{m}A_i^{k + 1}x^k}{k!} \end{aligned} \] 很显然答案生成函数就是\(\sum_{i = 1}^n A_i(x)\prod_{j\neq i} B_i(x)\)。然后下面先考虑一下那个\(A_i(x)\)……注意到他的系数全都和\(k + 1\)有关，但是\(x\)的次数为\(k\)，因此用积分将其右移（记\(C_i(x) = \int A_i(x)\mathrm{d}x\)）： \[ \begin{aligned} C_i(x) &= \sum_{k = 1}^{+\infty} \frac{k^{2m} A_i^k x^k}{k!}\\ &=\sum_{k = 0}^{+\infty} \frac{k^{2m} A_i^k x^k}{k!}\\ &=\sum_{k = 0}^{+\infty}\frac{(A_ix)^k}{k!}\sum_{j = 0}^{2m}\begin{Bmatrix}2m\\ j\end{Bmatrix}k^{\underline{j}}\\ &=\sum_{j = 0}^{2m}\begin{Bmatrix}2m\\ j\end{Bmatrix}j!\sum_{k = 0}^{+\infty}\frac{(A_ix)^k}{k!}\binom{k}{j}\\ &=\sum_{j = 0}^{2m}\begin{Bmatrix}2m\\ j\end{Bmatrix}j!\cdot\frac{A_i^jx^j}{j!}e^{A_ix}\\ &=\sum_{j = 0}^{2m}\begin{Bmatrix}2m\\ j\end{Bmatrix}A_i^jx^je^{A_ix} \end{aligned} \] 然后再推回去： \[ \begin{aligned} A_i(x) &= C_i'(x)\\ &= \sum_{j = 0}^{2m}\begin{Bmatrix}2m\\ j\end{Bmatrix}A_i^j(jx^{j - 1}e^{A_ix} + A_ix^je^{A_ix})\\ &= e^{A_ix}\sum_{j = 0}^{2m}\begin{Bmatrix}2m\\ j + 1\end{Bmatrix}(j + 1)A_i^{j + 1}x^j + \begin{Bmatrix}2m\\ j\end{Bmatrix}A_i^{j + 1}x^j\\ &= e^{A_ix}\sum_{j = 0}^{2m}A_i^{j + 1}\begin{Bmatrix}2m + 1\\ j + 1\end{Bmatrix}x^j \end{aligned} \] 最后一步用了第二类斯特林数的递推公式……类似的我们可以得到\(B_i(x)=e^{A_ix}\sum_{j = 0}^{m}A_i^{j + 1}\begin{Bmatrix}m + 1\\ j + 1\end{Bmatrix}x^j\)。
然后我们提出所有的\(e^{cx}\)的形式，然后剩下的东西就全都是\(2m\)次以下的多项式了……
最后我们发现我们要求类似于\(\sum_{i = 1}^n A_i(x)\prod_{j\neq i}B_i(x)\)这样的形式，分治FFT一下即可。
注意常数啊……这玩意卡常剧毒。讲个笑话，我ban掉NTT的循环展开之后卡过了最后一个点……
Code
1 |
|