多项式入门

常见导数

首先铺垫一些基本函数的导数³：

$$\begin{aligned} (x^n)' &= nx^{n-1}\\ |x|' &= \operatorname{sgn}x\\ (e^x)' &= e^x\\ (a^x)' &= e^{x\ln a}\ln a\\ (\ln x)' &= \frac{1}{x}\\ (f^n(x))' &= nf'(x)(f^{n-1}(x)) \end{aligned}$$

多项式积分

$$\int F(x)\text{d}x=\int\sum_{i\ge 0}a_ix^i\text{d}x=\sum_{i\ge 1}\frac{a_{i-1}}{i}x^i$$

泰勒展开

泰勒展开可以将一个函数表示为无穷级数，也称为泰勒级数（Taylor Series）¹：

$$f(x)=\sum_{n\ge 0}\frac{f^{(n)}(x_0)}{n!}(x-x_0)^n$$

其中比较常用的是$f(x)$在$x_0=0$处的展开，也称麦克劳林展开：

$$f(x)=\sum_{n\ge 0}\frac{f^{(n)}(0)}{n!}x^n$$

多项式牛顿迭代

牛顿迭代法本用于逼近方程的根，而多项式牛顿迭代²则指在多项式环上求出模$x^n$意义下的根。实际上$n$越大那么求出的根越接近真实的根，这与牛顿迭代法是类似的。

已知函数$G$，求多项式$F$，使得

$$G(F(x))=0\pmod{x^n}$$

考虑倍增。假设我们求出了$F_0$使得$G(F_0(x))=0\pmod{x^{\left\lceil\frac{n}{2}\right\rceil}}$。

首先注意到$G(F(x))=0\pmod{x^{\left\lceil\frac{n}{2}\right\rceil}}$，因此$F\bmod x^{\left\lceil\frac{n}{2}\right\rceil}=F_0$，即他们的低位是一样的。

考虑将$G(F(x))$在$F_0(x)$处泰勒展开：

$$G(F(x))=\sum_{i\ge 0}\frac{G^{(i)}(F_0(x))}{i!}(F(x)-F_0(x))^i\pmod{x^n}$$

注意到$F(x)-F_0(x)$把低位都减没了。$(F(x)-F_0(x))^2$的最低次数项的次数都是$x^n$，因此可以直接忽略了。即

$$G(F(x))=G(F_0(x)) + G^{'}(F_0(x))(F(x)-F_0(x))\pmod{x^n}$$

因为$G(F(x))=0$，化简得到

$$F(x)=F_0(x)-\frac{G(F_0(x))}{G^{'}(F_0(x))} \pmod{x^n}$$

也可以简记为

$$F=F_0-\frac{G\circ F_0}{G'\circ F_0}\pmod{x^n}$$

牛迭与多项式牛迭

接触过牛顿迭代的读者会知道，对于一个连续且单调的函数$f(x)$，我们要求$f(x)=0$的近似解，则迭代的公式为

$$x_i=x_{i-1}-\frac{f(x_{i-1})}{f'(x_{i-1})}$$

牛顿迭代可以直观理解：如果当前位置的点值和导数点值同号，说明在根的右边；否则说明在根的左边。

那么多项式牛顿迭代又怎么直观理解呢？

多项式环是没有数轴的说法的。不过我们可以把它看作是向一个多项式逼近的过程，就像泰勒展开一样。$F_0$变成$F$，代入$0<x<1$，它的增量是不断变小（收敛）的。如果$x>1$的话是发散的，这不在我们讨论的范围中。也就是说在$0<x<1$的时候，多项式的高次项对点值的影响就越小。因此倍增牛迭可以理解为是添加高次项来逼近多项式。

接下来我们来看一下多项式牛顿迭代的应用。

多项式求逆

求模意义下多项式的逆。形式化地说：对于多项式$H(x)$，求出$F(x)$使得$F(x) H(x) = 1 \pmod {x^n}$。

首先介绍$O(n^2)$求逆的算法。

设$H(x) = \sum_{i\ge 0} h_ix^i$，$F(x) = \sum_{i\ge 0}f_i x^i$。

那么$f_0 = \frac{1}{h_0}$。对于$i>0$，有$\sum_{j=0}^i h_j f_{i-j} = 0$。即$f_i = -\frac{1}{h_0}\sum_{j=1}^i h_j f_{i-j}$。这样就可以递推求出$F(x)$。

使用牛顿迭代法可以更快。

设$G(F(x)) = \frac{1}{F(x)}-H(x)$。

那么问题转化为了求满足$G(F(x))=0\pmod{x^n}$的解。应用牛顿迭代得到

$$\begin{aligned} F(x)&=F_0(x)-\frac{G(F_0(x))}{G'(F_0(x))}\\ &=F_0(x)-\frac{F_0^{-1}(x)-H(x)}{-F_0^{-2}(x)}\\ &=2F_0(x)-H(x)F_0^2(x) \end{aligned}$$

那么使用 FFT/NTT 即可在$O(n\log_2n)$的时间内计算。

多项式开方

求$h(x)$的平方根。即求一个多项式$F(x)$使得$F^2(x) = h(x) \pmod {x^n}$。

与求逆类似，我们仍然可以递推地在$O(n^2)$时间内求出$F(x)$。

仍然考虑多项式牛迭。

设$G(F(x))=F^2(x)-h(x)$。应用牛顿迭代得到

$$\begin{aligned} F(x)&=F_0(x)-\frac{G(F_0(x))}{G'(F_0(x))}\\ &=F_0(x)-\frac{F_0^2(x)-h(x)}{2F_0(x)}\\ &=\frac{F_0^2(x)+h(x)}{2F_0(x)} \end{aligned}$$

时间复杂度$O(n\log_2n)$。

多项式对数

考虑计算一个多项式的对数函数（ln），记作$\ln F(x)$。首先我们要了解$\ln F(x)$的级数形式。

考虑$\ln (1-x)$在原点的泰勒展开：

$$\ln(1-x)=-\sum_{i\ge 1}\frac{x^i}{i}$$

这样一来，我们就可以定义$\ln (1-F(x))$：

$$\ln(1-F(x))=-\sum_{i\ge 1}\frac{F(x)^i}{i}$$

换句话说对于$F(0)=1$的多项式，我们把它理解为$1-F_1(x)$的形式，就可以理解为上述定义。

之所以要求常数项是$1$，是因为$\ln 1 = 0$，不用考虑离散对数等等的问题。同时方便我们计算。

接下来考虑计算求出$\ln F(x)\pmod{x^n}$。首先做复合函数求导：

$$(\ln F(x))'=\frac{\text{d}\ln F(x)}{\text{d}x}=\frac{\text{d}\ln F(x)}{\text{d}F(x)}\frac{\text{d}F(x)}{\text{d}x}=\frac{F'(x)}{F(x)}$$

两边同时积分得到

$$\ln F(x)=\int\frac{F'(x)}{F(x)}\text{d}x$$

这样就可以用多项式求逆来计算了。这样计算的一个问题是，求导再积分后，常数项就没了。如果$F(0)=1$就会比较好办，此时$\ln F(x)$的常数项为$0$。

除此之外，我们仍然可以递推求解$\ln F(x)$。设$\ln F(x) = \sum_{i\ge 1} g_i x^i$，$F(x) = \sum_{i\ge 0}f_i x^i$（$f_0 = 1$）。

根据$(\ln F(x))' F(x) = F'(x)$，对于$i > 0$有$\sum_{j=0}^i g_{j+1}(j+1) f_{i-j} = f_{i+1}(i+1)$。

整理一下得到$g_i = f_i - \frac{1}{i} \sum_{j = 1} ^ {i-1} j\cdot g_j\cdot f_{i-j}$。这样就可以$O(n^2)$递推了。

注：

$$\ln x=\sum_{i\ge 1}\frac{1}{i}\left( \frac{x-1}{x} \right)^i\qquad \forall Re(x)\ge \frac{1}{2}.$$

多项式指数

考虑计算一个多项式的指数函数⁴（exp），记作$\exp F(x)$或者$e^{F(x)}$。

仿照$\ln F(x)$的定义，我们将$\exp x=e^x$在原点泰勒展开得到

$$\exp x=\sum_{i\ge 0}\frac{e^0}{i!}x^i=\sum_{i\ge 0}\frac{x^i}{i!}$$

因此可以得到

$$\exp F(x)=\sum_{i\ge 0}\frac{F^i(x)}{i!}$$

考虑求$\exp H(x)\pmod {x^n}$。设$G(F(x))=\ln F(x)-H(x)\pmod{x^n}$。应用牛顿迭代得到

$$\begin{aligned} F(x)&=F_0(x)-\frac{G(F_0(x))}{G'(f_0(x))}\\ &=F_0(x)-\frac{\ln F_0(x)-H(x)}{\frac{1}{F_0(x)}}\\ &=F_0(x)(1-\ln F_0(x)+H(x)) \end{aligned}$$

容易发现在$H(x)$常数项为$0$时上式是容易计算的。

时间复杂度$O(n\log_2n)$。

再考虑递推求解$e^{F(x)}$。考虑求导：$(e^{F(x)})' = e^{F(x)} F'(x)$。

设$e^{F(x)} = \sum_{i \ge 0} g_i x^i$，$F(x) = \sum_{i \ge 0} f_i x^i$，那么$g_{i+1}(i+1) = \sum_{j=0}^i f_{j+1}(j+1) g_{i-j}$。

整理一下有$g_i = \frac{1}{i} \sum_{j=0}^{i-1} f_{j+1}(j+1)g_{i-j-1}$（$i>0$），当$f_0 = 0$时有$g_0 = 1$。

模板代码

¹. https://en.wikipedia.org/wiki/Taylor_series ↩

². http://blog.miskcoo.com/2015/06/polynomial-with-newton-method#i-4 ↩

³. https://zh.wikipedia.org/wiki/%E5%AF%BC%E6%95%B0%E5%88%97%E8%A1%A8 ↩

⁴. https://zh.wikipedia.org/wiki/%E6%8C%87%E6%95%B0%E5%87%BD%E6%95%B0 ↩