多项式初等函数

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

为了保证收敛，我们人为规定：若 \(G=\exp(F)\)，即 \(F=\ln(G)\)，那么有 \([x^0]F=0,~[x^0]G=1\)。

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

多项式牛顿迭代

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

考虑方程 \(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}}\)，那么和式只有前两项有用，由此可以推出上式。不难说明得到的 \(X\) 是满足 \(X\equiv X_0\pmod{x^{n/2}}\) 的唯一解。

一般的，我们容易知道方程解的常数项，于是可以根据常数项递推出整个解。

考虑函数 \(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)\)。其中初值 \([x^0]X=([x^0]F)^{-1}\)

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

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

因此

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

考虑函数 \(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} \]

初值 \([x^0]X=1\) 由定义给出。

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\) 大小会减半。