自动搬运

查看原文

来自洛谷，原作者为

	joke3579 **

搬运于2025-08-24 22:16:52，当前版本为作者最后更新于2024-07-01 14:24:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

怎么所有题解都没突破 $\widetilde O(n^2)$ 的 bound 啊？本题解做法的复杂度为 $O(n\log^2 n \log m)$。

令 $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)$，其为有标号有根树的生成函数，因此有 $[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)$ 还能不能加速啊？

核心代码：

signed main() {
    int n, k;
    cin >> n >> k;
	k --;
    poly f1(n + 2);
    rep(i,1,n + 1) f1[i] = 1ll * qp(i, i - 1) * gifc(i) % mod;
	
    poly ans(n + 2), tmp(n + 2); 
	ans[1] = 1;
	rep(i,1,n + 1) {
		tmp[i] = gifc(i - 1);
		if (!(i & 1)) tmp[i] = mod - tmp[i];
	}
	while (k) {
		if (k & 1) ans = ans.composite(tmp);
		tmp = tmp.composite(tmp);
		k >>= 1;
	}
	ans = ans.composite_inv();
	f1 = ans.composite(f1);
	f1 = (f1 << 1).ln();
	cout << 1ll * f1[n] * gfac(n) % mod << endl;
}