[洛谷P4002][清华集训2017]生成树计数

这个题半年前某金牌爷讲的时候我完全听不懂,但是昨天想了一下这个题,发现貌似并不难,只是有点复杂。
根据prufer序列,设第i种元素在prufer序列中出现了$c_i$次,那么这个prufer序列的贡献为:
$$\Big( \displaystyle\prod_{i=1}^n (c_i+1)^m \Big) \Big( \displaystyle\sum_{i=1}^n (c_i+1)^m \Big) \Big( \displaystyle\sum_{i=1}^n a_i^{c_i+1}\Big)$$
考虑枚举合法的$c_i$数组,那么答案为:
$$(n-2)!\displaystyle\sum_{c} \Big( \Big( \displaystyle\prod_{i=1}^n (c_i+1)^m \Big) \Big( \displaystyle\sum_{i=1}^n (c_i+1)^m \Big) \Big( \displaystyle\sum_{i=1}^n a_i^{c_i+1}\Big) \frac{1}{c_i!}\Big)$$
部分分一档一档来,拿前两档只要用一个dp暴力枚举下一个元素的出现次数统计进答案,然后用FFT优化即可。
显然这个dp没有优化空间,所以我们来考虑$m=1$的情况。
此时,
$$\Big( \displaystyle\sum_{i=1}^n (c_i+1)^m \Big)=2n-2$$
这一项是定值,我们考虑其它的项。
$$\Big( \Big( \displaystyle\prod_{i=1}^n (c_i+1) \Big) \Big( \displaystyle\sum_{i=1}^n a_i^{c_i+1}\Big) \frac{1}{c_i!}\Big)$$
考虑把问题转化为多项式,计算每个元素的生成函数,设第$t$个元素的生成函数为$F_t(x)$,其中第i项的系数就是出现i次的贡献。
答案就是
$$\Big( \displaystyle\prod_{i=1}^n F_i(x) \Big) [n-2]$$
那么我们有:

$$F_t(x)=\displaystyle\sum_{i=0}^{\infty} \frac{(i+1)a_t^{i+1}x^i}{i!}$$
$$=a_i\displaystyle\sum_{i=0}^{\infty}\frac{a_t^ix^i}{i!}+a_t^2x\displaystyle\sum_{i=1}^{\infty} \frac{a_t^{i-1}x^{i-1}}{(i-1)!}$$
$$=a_t(a_tx+1)e^{a_tx}$$
那么答案就是:
$$\Big( e^{(\sum_{i=1}^n a_ix)}\displaystyle\prod_{i=1}^n a_i(a_ix+1) \Big)[n-2]$$
我们只需要使用一次多项式exp和一次分治FFT即可求出答案。
仔细一想我们会发现:
$$\displaystyle\sum_{i=0}^{\infty} \frac{i^{\underline{k}}a_t^{i+1}x^i}{i!}$$
$$=a_t^{k+1}x^ke^{a_tx}$$
这意味着,如果我们要对任意的m求
$$\Big( \Big( \displaystyle\prod_{i=1}^n (c_i+1)^m \Big) \Big( \displaystyle\sum_{i=1}^n a_i^{c_i+1}\Big) \frac{1}{c_i!}\Big)$$
我们单个元素的生成函数一定可以化为$G(x)e^{a_tx}$的形式,其中$G(x)$是一个m次多项式,我们可以暴力将$(i+1)^m$化成下降幂多项式求出$G(x)$,然后使用分治FFT+多项式exp求解。
但是我们无法处理
$$\Big( \displaystyle\sum_{i=1}^n (c_i+1)^m \Big)$$
暴力对生成函数加上这一项会发现其实这是暴力枚举每一个元素,然后让这个元素的生成函数中的$m$变成$2m$,其他不变,然后乘起来,再将所有的这个乘积结果加起来。
我们发现这其实是只取一个元素的答案,我们可以用类似DP的方式进行解决,就是记录两个多项式,分别表示当前包含的元素中是否有取过2m的。然后直接分治的时候把两个多项式都作为关键字合并答案。
然后我惊奇地发现这道题切掉了。
时间复杂度$O(nm\lg^2 n)$,主要时间复杂度是分治FFT。

Tagged with:

发表评论