所以为什么不使用 2log 多项式复合呢？

· · 题解

怎么所有题解都没突破 \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;
}