多项式基础(从零开始)

本文将介绍一些关于多项式的基础内容并记录下笔者从零开始学习多项式的过程。

快速傅立叶变换以及多项式乘法

多项式的系数表示和点值表示

对于n​次多项式F(x)=\sum_{i=0}^na_ix^i​,我们称\{a_0,a_1,\cdots,a_n\}​为它的系数表示。

如果选用n+1个不同的数x_0,x_1,\cdots,x_n代入多项式求值得到n+1个值,我们称\{(x_i,F(x_i))|i=0,1,\cdots,n\}为它的一个点值表示。

对于已知系数表示的多项式,我们可以通过多项式多点求值的方法得到它的点值表示。反之,对于已知点值表示的多项式,我们可以通过多项式插值的方法得到它的系数表示。

单位根

n次单位根是n次幂为1的复数。它们位于复平面的单位圆上,构成正n边形的顶点,其中一个是1

n次单位根有n个,为e^{\frac{2\pi ki}{n}}\ (k=0,1,2,\cdots,n-1)

为了方便,我们设\omega_n=e^{\frac{2\pi i}{n}},那么单位根可以表示为\omega_n^i\ (i=0,1,2,\cdots,n-1)

多项式乘法

对于两个多项式A(x)=\sum_{i=0}^na_ix^i,B(x)=\sum_{i=0}^mb_ix^i相乘得到C(x)=\sum_{i=0}^{n+m}c_ix^i
c_i=\sum_{j+k=i,0\leq j\leq n,0\leq k\leq m}a_jb_k
如果直接计算复杂度是O(n^2)。我们可以先把A(x),B(x)转成点值表示再对位相乘得到C(x)的点值表示,然后再得到系数表示。这些操作可以通过快速傅立叶变换完成。

快速傅立叶变换

快速傅立叶变换有两个部分DFTIDFT。前者是求A(x)的点值表示,后者是将点值表示转化成系数表示。两者分别在O(nlogn)的时间复杂度内完成。

DFT

为了方便,我们先将多项式的次数补成2^k-1。设多项式次数为n-1。我们选取nn次单位根代入求点值表示。我们将利用单位根的性质优化复杂度。

先将每一项按照指数奇偶分类。
\begin{aligned} A(\omega_n^k)&=\sum_{i=0}^{n-1}a_i\omega_n^k\\ &=\sum_{i=0}^{\frac{n}{2}-1}a_{2i}\omega^{2i}+\sum_{i=0}^{\frac{n}{2}-1}a_{2i+1}\omega^{2i+1}\\ \end{aligned}
由于\omega_n^{2i}=\omega_{\frac{n}{2}}^i并且\omega_n^{k+\frac{n}{2}}=-\omega_n^{k},所以对于k<\frac{n}{2}时, A(\omega_n^k) = \sum_{i=0}^{\frac{n}{2}-1}a_{2i}\omega_{\frac{n}{2}}^{ki}+\omega_n^{k}\sum_{i=0}^{\frac{n}{2}-1}a_{2i+1}\omega_{\frac{n}{2}}^{ki} \begin{eqnarray*} A(\omega_n^{k+\frac{n}{2}}) &=& \sum_{i=0}^{\frac{n}{2}-1}a_{2i}\omega_{\frac{n}{2}}^{ki}+\omega_n^{k+\frac{n}{2}}\sum_{i=0}^{\frac{n}{2}-1}a_{2i+1}\omega_{\frac{n}{2}}^{ki} \\ &=&\sum_{i=0}^{\frac{n}{2}-1}a_{2i}\omega_{\frac{n}{2}}^{ki}-\omega_n^k\sum_{i=0}^{\frac{n}{2}-1}a_{2i+1}\omega_{\frac{n}{2}}^{ki} \end{eqnarray*} 所以我们,只需要代入\omega_{\frac{n}{2}}^0,\omega_{\frac{n}{2}}^1,\cdots,\omega_{\frac{n}{2}}^{\frac{n}{2}-1}\frac{n}{2}个值分别到左右两边的两个多项式中就可以求出点值。 我们可以容易的分析出复杂度T(n)=2T(\frac{n}{2})+O(n)=O(nlogn)

IDFT

IDFT的过程就是求解一个线性方程组 \begin{equation*} \left\{ \begin{array}{ccccccccc} a_0(\omega_n^0)^{0}&+&\cdots&+&a_{n-2}(\omega_n^0)^{n-2}&+&+a_{n-1}(\omega_n^0)^{n-1}&=&A(\omega_n^0) \\ a_0(\omega_n^1)^{0}&+&\cdots&+&a_{n-2}(\omega_n^1)^{n-2}&+&+a_{n-1}(\omega_n^1)^{n-1}&=&A(\omega_n^1) \\ \vdots & & \vdots & &\vdots& & \vdots & & \vdots\\ a_0(\omega_n^{n-1})^{0}&+&\cdots&+&a_{n-2}(\omega_n^{n-1})^{n-2}&+&+a_{n-1}(\omega_n^{n-1})^{n-1}&=&A(\omega_n^{n-1}) \end{array} \right. \end{equation*} 写成矩阵的形式就是 \begin{equation}\begin{bmatrix} (\omega_n^0)^0 & (\omega_n^0)^1 & \cdots & (\omega_n^0)^{n-1} \\ (\omega_n^1)^0 & (\omega_n^1)^1 & \cdots & (\omega_n^1)^{n-1} \\ \vdots & \vdots & \ddots & \vdots \\ (\omega_n^{n-1})^0 & (\omega_n^{n-1})^1 & \cdots & (\omega_n^{n-1})^{n-1} \end{bmatrix} \begin{bmatrix} a_0 \\ a_1 \\ \vdots \\ a_{n-1} \end{bmatrix} = \begin{bmatrix} A(\omega_n^0) \\ A(\omega_n^1) \\ \vdots \\ A(\omega_n^{n-1}) \end{bmatrix} \end{equation} 设上面的系数矩阵为E,我们构造矩阵D \begin{equation*} \mathbf D = \begin{bmatrix} (\omega_n^{-0})^0 & (\omega_n^{-0})^1 & \cdots & (\omega_n^{-0})^{n-1} \\ (\omega_n^{-1})^0 & (\omega_n^{-1})^1 & \cdots & (\omega_n^{-1})^{n-1} \\ \vdots & \vdots & \ddots & \vdots \\ (\omega_n^{-(n-1)})^0 & (\omega_n^{-(n-1)})^1 & \cdots & (\omega_n^{-(n-1)})^{n-1} \end{bmatrix} \end{equation*} P=D*E,可以发现 \begin{aligned} p_{ij}&=\sum_{k=0}^{n-1}d_{ik}e_{kj}\\ &=\sum_{k=0}^{n-1}(\omega_n^{-i})^k\cdot(\omega_n^{k})^j\\ &=\sum_{k=0}^{n-1}\omega_n^{k(j-i)} \end{aligned} 对于(j-i)!=0的情况,相当于在单位圆上绕了若干圈,最后和为0。所以p_{ij}=[i==j]*n。 所以原方程可以化为如下形式 \begin{equation} \begin{bmatrix} a_0 \\ a_1 \\ \vdots \\ a_{n-1} \end{bmatrix} = \frac{1}{n} \begin{bmatrix} (\omega_n^{-0})^0 & (\omega_n^{-0})^1 & \cdots & (\omega_n^{-0})^{n-1} \\ (\omega_n^{-1})^0 & (\omega_n^{-1})^1 & \cdots & (\omega_n^{-1})^{n-1} \\ \vdots & \vdots & \ddots & \vdots \\ (\omega_n^{-(n-1)})^0 & (\omega_n^{-(n-1)})^1 & \cdots & (\omega_n^{-(n-1)})^{n-1} \end{bmatrix} \begin{bmatrix} A(\omega_n^0) \\ A(\omega_n^1) \\ \vdots \\ A(\omega_n^{n-1}) \end{bmatrix} \end{equation} 也就是说 \begin{aligned} a_{i}&=\frac{1}{n}\sum_{k=0}^{n-1}A(\omega_n^{k})(\omega_n^{-i})^k \end{aligned} 我们把A(\omega_n^k)看成多项式的系数,把w_n^{-i}看作x,可以发现,若令G(x)=\sum_{k=0}^{n-1}A(w_n^k)x^k,那么a_i=\frac{G(w_n^{-i})}{n} 所以,IDFT的过程相当于是用\omega_n^{-i}代替\omega_n^i做了一遍DFT最后再除以n

多项式求逆

多项式的逆元

对于一个多项式A(x),如果存在B(x),deg_B\leq deg_A,使得 A(x)B(x)\equiv1\pmod {x^n} 我们就称B(x)A(x)\pmod {x^n}意义下的逆元,记作A^{-1}(x)

求解方法

多项式求逆元是一个倍增的过程,我们先考虑\pmod x意义下的逆元 A(x)\equiv a_0 \pmod x 所以 A^{-1}(x)\equiv a_0^{-1} \pmod x 现在我们考虑求解\pmod {x^{k},k>1}意义下的逆元,设其为B(x)

我们已经求解出\pmod {x^{\frac{k}{2}}}意义下的逆元,设其为B'(x),我们可以做出以下推导。(以下若无特殊说明,\frac{n}{2}表示)
A(x)B(x)\equiv1 \pmod{x^k}\\ A(x)B'(x)\equiv 1\pmod{x^{\frac{k}{2}}}
两式相减可以得到
A(x)(B(x)-B'(x))\equiv0\pmod{x^{\frac{k}{2}}}
所以
B(x)-B'(x)\equiv0\pmod{x^{\frac{k}{2}}}
由于等式右边是0,所以我们可以平方得到
B^2(x)-2B(x)B'(x)+B’^2(x)\equiv\pmod{x^k}

通过移项可以得到
B(x) \equiv 2B'(x) – A(x)B’^2(x) \pmod {x^k}
复杂度T(n)=T(\frac{n}{2})+O(nlogn)=O(nlogn)

求解多项式除法与多项式取模

多项式除法与取模

对于一个n次多项式A(x)和一个m,(m\leq n)次多项式B(x),存在两个多项式D(x),R(x),满足
A(x)=D(x)B(x)+R(x)
并且deg_R

求解方法

考虑如何把R(x)从式子中去掉,这样就变成多项式求逆元问题,可以在O(nlogn)的时间内完成。

我们发现对于一个n次多项式A(x)来说,x^nA(\frac{1}{x})相当于把A(x)的系数反转,我们把它记做A^R(x)

考虑在等式两边同时乘上x^n,然后把x换成\frac{1}{x},静观其变
x^nA(\frac{1}{x})=x^{n-m}D(\frac{1}{x})x^mB(\frac{1}{x})+x^nR(\frac{1}{x})\\ A^R(x)=D^R(x)B^R(x)+x^nR(\frac{1}{x})
显然deg_{D^R(x)}=n-m。而因为deg_R,所以R(\frac{1}{x})的最低项的次数不会小于-m+1,所以x^n*R(\frac{1}{x})的最低项次数不会小于n-m+1。所以,如果我们在\pmod{x^{{n-m+1}}}意义下计算就可以不管R(x),并且不会对D(x)产生影响。也就是说
A^R(x)\equiv B^R(x)D^R(x)\pmod{x^{n-m+1}}
我们只需要求出B^R(x)的逆元再求出D^R,回带求出P(x)即可。

复杂度O(nlogn)

多项式多点求值和快速插值

多项式多点求值

对于一个多项式A(x),给定n个值x_0,x_1,\cdots,x_{n-1},求A(x_0),A(x_1),\cdots,A(x_{n-1})

直接暴力是O(n^2)的,我们考虑用分治的方法,把系数和要代入的值的规模都减半,递归下去做。

考虑能不能求出两个多项式A_0(x),A_1(x),使得它们的次数都是A(x)的一半,并且A(x_i)=A_0(x_i),(0\leq i<\frac{n}{2})以及A(x)=A_1(x),(\frac{n}{2}\leq i

通过一定的观察,我们不难发现可以构造这两个多项式
P_0(x)=\prod_{i=0}^{\frac{n}{2}-1}(x-x_i)\\ P_1(x)=\prod_{i=\frac{n}{2}}^{n-1}(x-x_i)
可以得到
A(x)=P_0(x)D_0(x)+A_0(x)\\ A(x)=P_1(x)D_1(x)+A_1(x)
也就是说
A_0(x)\equiv A(x) \pmod{P_0(x)}\\ A_1(x)\equiv A(x) \pmod{P_1(x)}
于是我们就可以通过多项式取模完成一次分治操作。

其中的P_0(x)P_1(x)可以通过分治FFT预处理在O(nlog^2n)的复杂度完成。

复杂度T(n)=2T(n/2)+O(nlogn)=O(nlog^2n)

多项式快速插值

给一个大小为n的集合X=\{x_i,0\leq i以及Y=\{A(x_i),0\leq i

通过拉格朗日插值我们可以做到O(n^2)的复杂度。

同样的,我们考虑用分治方法来完成。
X_0=\{x_i,0\leq i<\frac{n}{2}\}\\ X_1=\{x_i,\frac{n}{2}\leq i
假设我们已经求出A_0(x)​,我们考虑如何构造出A(x)​,我们设
P_0(x)=\prod_{i=0}^{\frac{n}{2}-1}(x-x_i)
我们构造
A(x)=A_1(x)P(x)+A_0(x)
显然,这个式子对于集合X_0恒成立,我们再考虑对于集合X_1
A_1(x_i)=\frac{A(x_i)-A_0(x_i)}{P(x_i)}
这样,就可以通过\{(x_i,\frac{A(x_i)-A_0(x_i)}{P(x_i)}),\frac{n}{2}\leq i这几个值来插值递归求出A_1(x)

由于分治的每一步都需要多点求值,所以复杂度为T(n)=2T(n/2)+O(nlog^2n)=O(nlog^3n)

听说有O(nlogn^2)的做法,留坑待填。

发表评论

电子邮件地址不会被公开。 必填项已用*标注