概述

给定一个 $n - 1$ 次多项式 $A(x)$，你需要求出多项式 $B(x)$ 满足 $B(x) \equiv \exp(A(x)) \pmod{x ^ n}$。其中保证 $[x ^ 0]A(x) = 0$。

思路

按照套路先对两边同时取自然对数，得到：

$$ \ln B(x) \equiv A(x) \pmod{x ^ n} $$

变形得到：

$$ \ln B(x) - A(x) \equiv 0 \pmod{x ^ n} $$

定义函数 $G(F(x)) = \ln F(x) - A(x)$，参考「算法笔记」泰勒公式和牛顿迭代法 中的式子可以得到：

$$ F(x) \equiv F_0(x) - \frac{G(F_0(x))}{G'(F_0(x))} \pmod{x ^ n} $$

直接倍增计算，边界为 $n = 1$ 时 $F(x) = 1$。

时间复杂度：$\mathcal O(n \log n)$。

代码

Vec exp(Vec A) {
    assert(A[0] == 0);
    int n = A.size(), N = extend(n);
    A.resize(N);
    Vec E(N, 0);
    E[0] = 1;
    for (int l = 2; l <= N; l <<= 1) {
        Vec P = (-ln(fix(E, l)) + fix(A, l) + 1) * fix(E, l);
        std::copy(P.begin(), P.begin() + l, E.begin());
    }
    E.resize(n);
    return E;
}