多项式ln & exp

给出 \(F(x)\),求 \(G(x)\) 满足 \(\ln(F(x))-G(x) \equiv 0 \ (mod\ x^n)\)。

$$
G'(x) \equiv \frac{F'(x)}{F(x)}\\
G(x) \equiv \int \frac{F'(x)}{F(x)} dx$$

复杂度 \(O(nlogn)\)。


给出 \(F(x)\),求 \(G(x)\) 满足 \(e^{F(x)}-G(x) \equiv 0\ (mod\ x^n)\)。

同时取 \(\ln\)。
$$F(x)-\ln(G(x)) \equiv 0\ (mod\ x^n)$$

带入牛顿迭代式
$$\begin{align}
G_{t+1}(x) & = G_t(x)-\frac{F(x)-\ln(G_t(x))}{-\frac{1}{G_t(x)}}\ (mod\ {x^{2^{t+1}}}) \\
& = G_t(x)+G_t(x)(F(x)-\ln(G_t(x)))\ (mod\ {x^{2^{t+1}}}) \\
\end{align}$$

复杂度 \(O(nlogn)\)。

代码实现丑陋,求逆和求 \(\exp\) 都要先扩到 \(2\) 的幂QAQ。


在《多项式ln & exp》上留下第一个评论