多项式初等函数

在模 \(x^n\) 意义下的多项式形成一个交换环，常数项非零的多项式有唯一乘法逆元。仿照高数的定义，定义多项式的积分，求导。由泰勒展开定义多项式的 \(\ln,\exp\)，收敛应该是定义为模意义下的收敛。

为了便于书写，下文中的大写字母一般都是多项式。

多项式牛顿迭代

这个东西可以推出很多式子。

考虑方程 \(G(X)\equiv 0\pmod{x^n}\)。如果我们已知 \(G(X)\equiv 0\pmod{x^{n/2}}\) 的解 \(X_0\)，那么可以根据如下公式得到原方程的一组解 \(X\)：

\[ \boxed{X=X_0-\frac{G(X_0)}{G'(X_0)}} \]

证明：将 \(G(X)\) 在 \(X_0\) 处展开：

\[ G(X)\equiv \sum_{i=0}^{\infty}\frac{G^{(i)}(X_0)}{i!}(X-X_0)^i\pmod {x^n} \]

令 \(X\equiv X_0\pmod {x^{n/2}}\)，那么和式只有前两项有用，由此可以推出上式。因此不难说明每个 \(G(X)\equiv 0\pmod {x^1}\) 的初值 \(X\) 唯一对应一组模 \(x^n\) 的解。

求逆

考虑函数 \(G(X)=\frac{1}{X}-F\)，那么方程 \(G(X)\equiv 0\) 的解就是 \(F\) 的乘法逆。直接带入 Newton's method 即可得到倍增式子：

\[ X'=X-\frac{\frac{1}{X}-F}{-\frac{1}{X^2}}=\boxed{2X-FX^2} \]

时间复杂度 \(T(n)=T(\frac{n}{2})+O(n\log n)\)，易得 \(T(n)=O(n\log n)\)。

ln

已知 \(X\)，欲求 \(\ln(X)\)。对 \(x\) 求导：

\[ \frac{\text d}{\text dx}\ln(X)=\frac{X'}{X} \]

因此

\[ \boxed{\ln(X)=\int\frac{X'}{X}dx} \]

exp

考虑函数 \(G(X)=\ln(X)-F\)，那么 \(G(X)\equiv 0\) 的解就是 \(\exp(F)\)。带入 Newton's method：

\[ X'=X-\frac{\ln(X)-F}{\frac{1}{X}}=\boxed{X-X\ln X+FX} \]

波斯坦-茉莉（Bostan-Mori）

Bostan-Mori 可以在 \(O(n\log n\log m)\) 的复杂度内提取 \([x^m]\frac{P(x)}{Q(x)}\)，其中 \(P(x),Q(x)\) 是次数不超过 \(n\) 的多项式，\(m\) 是一个很大的数。

具体怎么做的呢？考虑将分式上下同时乘以 \(Q(-x)\)，不难发现 \(Q(x)Q(-x)\) 只剩偶数项，所以式子可以表示如下：

\[ \frac{P(x)}{Q(x)}=\frac{P(x)Q(-x)}{Q(x)Q(-x)}=\frac{H_0(x^2)+xH_1(x^2)}{G(x^2)} \]

此时按照 \(m\) 的奇偶性把 \(H_0(x^2),xH_1(x^2)\) 扔掉一项即可，\(m\) 大小会减半。