概述

给定一个 $n - 1$ 次多项式 $A(x)$，你需要求出一个多项式 $B(x)$ 满足 $B(x) \equiv \ln A(x) \pmod{x ^ n}$。

思路

两边同时求导，通过链式法则 $f(x) = g(h(x)) \rightarrow \frac{\mathrm{d}f}{\mathrm{d}x} = \frac{\mathrm{d}g}{\mathrm{d}h} \cdot \frac{\mathrm{d}h}{\mathrm{d}x}$ 可以得到：

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

由于求导和不定积分是互逆的，则 $B(x) = \int B'(x) \mathrm{d}x$。直接套上求逆的板子即可。

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

代码

Vec ln(Vec A) {
    assert(A[0] == 1);
    int n = A.size();
    return inte(fix(der(A) * ~A, n));
}