标签：langle frac log 闲话 24.7 right exp rangle

闲话

待补

推歌：滴答滴答 by 星葵 et al. feat. 洛天依V5 Nature
抓住你的耳朵！

败祭

昨天 jjdw 水了一篇闲话。那我就来补完一下做法吧（
感谢大自然的馈赠

P6049 燔祭

计数 \(n\) 个点的有标号有根树，满足点权为 \([1,m]\) 内整数，且满足大根堆性质。对 \(998244353\) 取模。

\(n\le 10^5, m \le 10^9\)，时限 \(25s\)。

呃呃 这个加强版 我都觉得难蚌

令 \(F_k(x)\) 是根的权为 \(k\) 的树的个数的 EGF，则枚举一列无序合法子树容易得到：

\[F_k(x)=x\exp\sum_{i=1}^kF_i(x) \]

也就是：

\[\begin{aligned}F_k(x)&=x\exp F_k(x)\exp\sum_{i=1}^{k-1}F_i(x)\\&=F_{k-1}(x)\exp F_k(x)\end{aligned} \]

即 \(\dfrac{F_k}{\exp F_k}=F_{k-1}\)。上式同时指出了 \(F_1(x) = x \exp F_1(x)\)，\(F_1(x)\) 为有标号有根树的生成函数，\([x^n/n!] F_1(x) = n^{n - 1}\)。

令 \(f(x) = xe^{-x}\)，记 \(f\) 复合自身 \(k\) 次得到的函数为 \(f^{\langle k\rangle}\)，我们知道 \(F_1(x) = f^{\langle m - 1 \rangle}(F_{m}(x))\)，也就有 \(F_{m}(x) = f^{\langle 1 - m \rangle}(F_1(x))\)。下面只需要计算 \(f^{\langle m - 1\rangle}(x)\)，随后求复合逆再复合即可得到 \(F_m(x)\)。

答案为

\[\left[\frac{x^n}{n!}\right] \sum_{i = 1}^m F_i(x) = \left[\frac{x^n}{n!}\right]\ln\left(\frac{F_m(x)}{x}\right) \]

使用 \(O(n\log^2 n)\) 多项式复合(逆)技术，计算 \(f^{\langle m - 1\rangle}(x)\) 可以做到 \(O(n\log^2 n \log m)\)，剩余的部分均非复杂度瓶颈。

所以计算 \(f^{\langle m - 1\rangle}(x)\) 还能不能加速啊？有思路的可以和我交流

标签：langle,frac,log,闲话,24.7,right,exp,rangle
From： https://www.cnblogs.com/joke3579/p/18277469/chitchat240701