多项式从入门到进门

· · 个人记录

多项式全家福

多项式

一个以 x 为变量的多项式定义在一个代数域 F 上，将函数 A(x) 表示为形式和：

A(x)=\sum\limits_{i=0}^{n-1}a_ix^i

如果一个多项式的最高次的非零系数是 k，则称 A(x) 的次数为 k。任何严格大于一个多项式次数的整数都是该多项式的次数界。因此，对于次数界为 n 的多项式 C(x)，其次数可以是 0\sim n-1 之间的整数。

我们在多项式上可以定义很多不同的运算。

多项式加法

对于所有属于定义域的 x，都有 C(x)=A(x)+B(x)，即：

若

A(x)=\sum\limits_{i=0}^{n-1}a_ix^i B(x)=\sum\limits_{i=0}^{n-1}b_ix^i

则有

C(x)=\sum\limits_{i=0}^{n-1}C_ix^i

其中

c_i=a_i+b_i

多项式乘法

c_i=\sum\limits_{j=0}^ia_{j}b_{i-j}

多项式的表示

系数表达

对于一个次数界为 n 的多项式 A(x)，其系数表达式为一个由系数组成得到的向量：

a=(a_0,a_1,\cdots,a_{n-1}) A(x_0)=a_0+x_0(a_1+x_0(a_2+\cdots+x_0(a_{n-2}+x_0a_{n-1})\cdots))

类似的，对于两个分别用系数向量 a=(a_0,a_1,\cdots,a_{n-1}),b=(b_0,b_1,\cdots,b_{n-1}) 表示的多项式进行相加时，所需的时间是

乘法同理，此时 $c$ 也称为输入向量 $a,b$ 的卷积，记为 $c=a\otimes b$。 ### 点值表达 - 一个次数界为 $n$ 的多项式的点值表达就是一个有 $n$ 个点值对所组成的集合： $$\{(x_0,y_0),(x_1,y_1),\cdots,(x_{n-1},y_{n-1})\}$$ 使得对 $k=0,1,\cdots,n-1$ 所有 $x_k$ 各不相同且 $y_k=A(x_k)$。 一个多项式可以有很多不同的点值表达，因为可以采用 $n$ 个不同的点构成的集合作为这种表示方法的基。 朴素的求值是 $O(n^2)$ 的。 求值的逆称为插值。当插值多项式的次数界等于已知的点值对的数目时，插值才是明确的。 我们可以在用拉格朗日插值在 $O(n^2)$ 内插值。 - 以上求值和插值可以将多项式的系数表达和点值表达进行相互转化，上面给出的算法的时间复杂度是 $O(n^2)$，但我们可以巧妙地选取 $x_k$ 来加速这一过程，使其运行时间变为 $O(n\log n)$。 对于许多多项式相关的操作，点值表达式是十分便利的。 对于加法，如果 $C(x)=A(x)+B(x)$，且点值表达分别为： $$\{(x_0,y_0),(x_1,y_1),\cdots,(x_{n-1},y_{n-1})\}$$ $$\{(x_0,y'_0),(x_1,y'_1),\cdots,(x_{n-1},y'_{n-1})\}$$ 则 $C$ 的点值表达为： $$\{(x_0,y_0+y'_0),(x_1,y_1+y'_1),\cdots,(x_{n-1},y_{n-1}+y'_{n-1})\}$$ 乘法同理，此时需要 $2n$ 个点才能插出 $C$： $$\{(x_0,y_0y'_0),(x_1,y_1y'_1),\cdots,(x_{2n-1},y_{2n-1}y'_{2n-1})\}$$ 时间复杂度为 $O(n)$。 - 最后，我们考虑一个采用点值表达的多项式，如何求其在某个新点上的值。最简单的方法是把该多项式转成系数形式表达，然后在新点处求值。 ------------ ## DFT&FFT&IDFT ### 单位根 - 在复数域下，满足 $w^n=1$ 的 $w$ 被称为 $n$ 次单位根。 根据代数基本定理，$n$ 次单位根。一共有 $n$ 个，这些根为 $e^{\frac{2\pi ik}{n}}$。 $e^{\frac{2\pi i}{n}}$ 为主 $n$ 次单位根，所有其他 $n$ 次单位复数根都是$w_n$的幂次。 这 $n$ 个单位复数根在乘法意义下形成了一个群，而且均匀分布在以复平面的原点为圆心的单位半径的圆周上。 - 消去引理：对任何自然数 $n,k,d$，都有： $$w_{dn}^{dk}=w_n^k$$ ------------ ### DFT - 我们希望计算次数界为 $n$ 的多项式 $A(x)$ 在 $w_n^0,w_n^1,\cdots,w_n^{n-1}$ 处的值。 对于 $k=0,1,\cdots,n-1$，定义结果 $y_k$： $$y_k=A(w_n^k)=\sum\limits_{i=0}^{n-1}a_iw_n^{ki}$$ 向量 $y=(y_0,y_1,\cdots,y_{n-1})$ 即为系数向量 $a$ 的 DFT，也记为 $y=DFT_n(a)$。 ------------ ### FFT 利用单位复数根的特殊性质，我们可以在 $O(n\log n)$ 的时间内计算出 $DFT_n(a)$。设 $n$ 为 $2$ 的幂次。 - 我们利用分治： 令 $a=(a_0,a_2,\cdots,a_{n-1}),a_1=(a_0,a_2,\cdots,a_{n-2}),a=(a_1,a_2,\cdots,a_{n-1})

对于 k<\frac{n}{2}，我们有：

\begin{aligned}y_k&=A(w_n^k)\\&=\sum\limits_{i=0}^{n-1}a_iw_n^{ki}\\&=\sum\limits_{i=0}^{\frac{n}{2}-1}a_{2i}w_n^{2ki}+\sum\limits_{i=0}^{\frac{n}{2}-1}a_{2i+1}w_n^{2ki+k}\\&=\sum\limits_{i=0}^{\frac{n}{2}-1}a_{2i}w_n^{2ki}+w_n^k\sum\limits_{i=0}^{\frac{n}{2}-1}a_{2i+1}w_n^{2ki}\\&=\sum\limits_{i=0}^{\frac{n}{2}-1}a_{2i}w_{\frac{n}{2}}^{ki}+w_n^k\sum\limits_{i=0}^{\frac{n}{2}-1}a_{2i+1}w_{\frac{n}{2}}^{ki}\\&={y_1}_k+w_n^k{y_2}_k\end{aligned}

对于 k\geq \frac{n}{2}，我们有：

\end{aligned}

这样我们把 y_1,y_2 合并为 y_3 的时间复杂度是 O(n)。

所以总的时间复杂度为：

T(n)=2T(\dfrac{n}{2})+O(n)=O(n\log n)

IDFT

通过推导公式，我们可以得到：

a_k=\dfrac{1}{k}\sum\limits_{i=0}^{n-1}y_iw_n^{-ki}

所以我们可以用类似 FFT 的方法在 O(n\log n) 的时间内求出 IDFT_n(y)。

多项式乘法

我们可以在 O(n) 时间内补零，O(n\log n)内求值，O(n) 内点值乘法，O(n\log n) 内插值，所以我们可以在 O(n\log n) 内求出 a\otimes b，即：

a\otimes b=IDFT_{2n}\big(DFT_{2n}(a)\cdot DFT_{2n}(a)\big)

蝶形变换

我们发现，递归时 a 是长这样的：

\left[0\quad1\quad2\quad3\quad4\quad5\quad6\quad7\right] \left[0\quad2\quad4\quad6\right]\ \left[1\quad3\quad5\quad7\right] \left[0\quad4\right]\ \left[2\quad6\right]\ \left[1\quad5\right]\ \left[3\quad7\right] \left[0\right]\ \left[4\right]\ \left[2\right]\ \left[6\right]\ \left[1\right]\ \left[5\right]\ \left[3\right]\ \left[7\right]

三次变两次

按照上面的做法，我们要分别先求出 A(x),B(x) 的卷积，把它们分别FFT，然后对应每项乘起来，最后再逆FFT回来。

我们可以把 B(x) 放到 A(x) 的虚部上面去，求得 A(x)^2，然后把它的虚部取出来除以二就是答案了。

(a+bi)^2=(a^2-b^2)+(2abi)

这样我们就把常数优化到原来的 \frac{2}{3}。

NTT

先求出 p 的原根 g，不难发现 g^{\frac{p}{n-1}} 与 w_n 的性质类似，所以我们可以用 g^{\frac{p}{n-1}} 来代替 w_n。

多项式求导

A^{\prime}(x)=\sum\limits_{i\geq 1}ia_ix^{i-1}

多项式积分

\int A(x)=\sum\limits_{i\geq 1}\dfrac{a_{i-1}}{i}x^i

多项式牛顿迭代

考虑倍增。

首先当 n=1 时，\left[x^{0}\right]g(f(x))=0 的解需要单独求出。

将 g(f(x)) 在 f_{0}(x) 处进行泰勒展开，有：

\sum_{i=0}^{+\infty}\frac{g^{(i)}(f_{0}(x))}{i!}(f(x)-f_{0}(x))^{i}\equiv 0\pmod{x^{n}}

因为 f(x)-f_{0}(x) 的最低非零项次数最低为 \lceil\frac{n}{2}\rceil，故有：

\forall 2\leqslant i:((f(x)-f_{0}(x))^{i}\equiv 0\pmod{x^{n}}

则：

\sum_{i=0}^{+\infty}\frac{g^{(i)}(f_{0}(x))}{i!}(f(x)-f_{0}(x))^{i}\equiv g(f_{0}(x))+g'(f_{0}(x))(f(x)-f_{0}(x))\equiv 0\pmod{x^{n}} f(x)\equiv f_{0}(x)-\frac{g(f_{0}(x))}{g'(f_{0}(x))}\pmod{x^{n}}

多项式求逆

多项式 A(x) 存在乘法逆元的充要条件是其常数项存在乘法逆元。

g(f(x))=\frac{1}{f(x)}-h(x)\equiv 0\pmod{x^{n}}

应用牛迭可得：

\end{aligned}

时间复杂度为：

T(n)=O(n\log n)+T\left(\dfrac{n}{2}\right)=O(n\log n)

多项式开根

g(f(x))=f^{2}(x)-h(x)\equiv 0\pmod{x^{n}}

应用牛迭可得：

\end{aligned}

时间复杂度为：

T(n)=O(n\log n)+T\left(\dfrac{n}{2}\right)=O(n\log n)

多项式exp

g(f(x))=\ln{f(x)}-h(x)\pmod{x^{n}}

应用牛迭可得：

\begin{aligned}f(x)&\equiv f_{0}(x)-\frac{\ln{f_{0}(x)}-h(x)}{\frac{1}{f_{0}(x)}}&\pmod{x^{n}}\\&\equiv f_{0}(x)(1-\ln{f_{0}(x)+h(x)})&\pmod{x^{n}}\end{aligned}

时间复杂度为 O(n\log n)。

多项式快速幂

F(x)^k= \text e^{k\ln F(x)}

具体来讲，我们要找出最小的 t，满足 F(x) 的 t 次项不为 0，那么：

F(x)^k=\left(\frac{F(x)}{x^t} \right)^kx^{tk}

时间复杂度为 O(n\log n)。

多项式除法

发现若能消除 R(x) 的影响则可直接多项式求逆解决。

考虑构造变换 f^{R}(x)=x^{\operatorname{deg}{f}}f(\frac{1}{x}) 观察可知其实质为反转 f(x) 的系数。

设 n=\operatorname{deg}{f},m=\operatorname{deg}{g}。

将 f(x)=Q(x)g(x)+R(x) 中的 x 替换成 \frac{1}{x} 并将其两边都乘上 x^{n}，得到：

\begin{aligned}x^{n}f(\frac{1}{x})&=x^{n-m}Q(\frac{1}{x})x^{m}g(\frac{1}{x})+x^{n-m+1}x^{m-1}R(\frac{1}{x})\\f^{R}(x)&=Q^{R}(x)g^{R}(x)+x^{n-m+1}R^{R}(x)\end{aligned}

注意到上式中 R^{R}(x) 的系数为 x^{n-m+1}，则将其放到模 x^{n-m+1} 意义下即可消除 R^{R}(x) 带来的影响。

又因 Q^{R}(x) 的次数为 (n-m)<(n-m+1)，故 Q^{R}(x) 不会受到影响。

则：

f^{R}(x)\equiv Q^{R}(x)g^{R}(x)\pmod{x^{n-m+1}}

使用多项式求逆即可求出 Q(x)，将其反代即可得到 R(x)。

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