题解 P7275 【计树】

· · 题解

最终的树一定是若干条形如 l,l+1,\cdots,r 的极长链拼起来得到的，考虑容斥，一个基本单位是 \sum_{i\geq 2}x^i=\frac{x^2}{1-x}，我们容斥掉几个拼起来的情况，也就是

1-\frac{1}{1+\frac{x^2}{1-x}}=\frac{x^2}{1-x+x^2}

现在我们可以忽略极长这个限制，在乘上对应的容斥系数的情况下直接拼接. 根据 prufer 序列的经典结论，一个划分的拼接方案数是

n^{m-2}\prod_{i=1}^mlen_i

给出一个简单的证明: 我们把一个已经连好的连通块看成一个点，然后枚举其在树中的度数，每个度数有 len_i 种连法，那么根据 prufer 编码就有

\begin{aligned} &\sum_{\sum (deg_i-1)=m-2}\frac{(m-2)!}{\prod(deg_i-1)!}\prod len_i^{deg_i}\\ =&\left(\prod len_i\right)\left((m-2)![x^{m-2}]\prod e^{len_ix}\right)\\ =&n^{m-2}\prod_{i=1}^mlen_i \end{aligned}

我们把 n^{-2} 提到外面来，那么现在长为 len 的一段的贡献系数就是 f_{len}=\left([x^{len}]\frac{x^2}{1-x+x^2}\right)len\cdot n

最终的答案就是

[x^n]\frac{1}{1-\sum_{i\geq 2}f_ix^i}

可以多项式求逆做到 n\log n，不过事实上这是一个线性递推，证明如下:

考察 \frac{x^2}{1-x+x^2}，提出一个 x 之后它是线性递推的，而我们恰好不需要前两项系数. 于是我们知道 [x^n]\frac{x^2}{1-x+x^2} 在 n\geq 2 的时候具有 \alpha r_1^n+\beta r_2^n 的形式.

再考虑点乘上 i\cdot n 之后的结果，那就是

n\sum_{i\geq 2}i(\alpha r_1^i+\beta r_2^i)x^i

这必然可以被写成 \frac{P(x)}{Q(x)} 的形式，\frac{1}{1-F} 亦然. 将分子对分母取模就得到一个线性递推加常多项式的形式（不过在这题里最终分子次数是小于分母的）. 我们用次数高于常多项式次数的部分做线性递推即可. 使用 BM 算法求出递推式，最终复杂度 \Theta(\log n)

延伸阅读（雾）：https://blog.csdn.net/ei_captain/article/details/104288107