「Learning Notes」多项式 ln|exp

本文会随着笔者的水平提升持续更新.
若发现文中有叙述不严谨之处,欢迎指出。

Description

给定多项式 f(x) ,求模 x^{n} 意义下的 \ln{f(x)} \exp{f(x)}

Methods

普通方法


首先,对于多项式 f(x) ,若 \ln{f(x)} 存在,则由其定义,其必须满足:

\left[x^{0}\right] f(x) = 1

\ln{f(x)} 求导再积分,可得:

\begin{aligned} \left(\ln{f(x)}\right)' & \equiv \frac{f'(x)}{f(x)} & \pmod{x^{n}}\\ \ln{f(x)} & \equiv \int \frac{f'(x)}{f(x)} & \pmod{x^{n}} \end{aligned}

多项式的求导,积分时间复杂度为 O(n) ,求逆时间复杂度为 O(n \log{n}) ,故多项式求 \ln 时间复杂度 O(n \log{n})


首先,对于多项式 f(x) ,若 \exp{f(x)} 存在,则其必须满足:

\left[x^{0}\right] f(x) = 0

否则 \exp{f(x)} 的常数项不收敛.

\exp{f(x)} 求导,可得:

\exp'{f(x)} \equiv \exp{f(x)} f'(x) \pmod{x^{n}}

比较两边系数可得:

\left(n + 1\right) [x^{n}] \exp{f(x)} = \sum_{i = 0}^{n} [x^{i}] \exp{f(x)}\left(n - i + 1\right) \left[x^{n - i}\right] f(x)

\left[x^{0}\right] f(x) = 0 ,则:

\left(n + 1\right) [x^{n}] \exp{f(x)} = \sum_{i = 0}^{n - 1} [x^{i}] \exp{f(x)}\left(n - i + 1\right) \left[x^{n - i}\right] f(x)

使用分治 FFT 即可解决.

时间复杂度 O\left(n \log^{2}{n}\right)

Newton's Method

使用 Newton's Method 即可在 O(n \log{n}) 的时间复杂度内解决多项式 \exp

Examples

  1. 计算 f^{k}(x)

普通做法为多项式快速幂,时间复杂度 O\left(n \log{n} \log{k}\right)

  • \left[x^{0}\right] f(x) = 1 时,有:

f^{k}(x) = \exp{\left(k \ln{f(x)}\right)}

  • \left[x^{0}\right] f(x) \ne 1 时,设 f(x) 的最低次项为 f_{i} x^{i} ,则:

f^{k}(x) = f_{i}^{k} x^{ik} \exp{\left(k \ln{\frac{f(x)}{f_{i} x^{i}}}\right)}

时间复杂度 O(n \log{n})