「算法笔记」多项式自然对数

通过简单的求导和不定积分可以求出多项式的自然对数。


概述

给定一个 $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));
}

发表评论