多项式基础(从零开始)

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

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

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

对于$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)$的点值表示,然后再得到系数表示。这些操作可以通过快速傅立叶变换完成。

快速傅立叶变换

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

DFT

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

先将每一项按照指数奇偶分类。
$$
\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<m,deg_d= n-m$

求解方法

考虑如何把$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<m$,所以$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<n)$

通过一定的观察,我们不难发现可以构造这两个多项式
$$
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<n\}$以及$Y=\{A(x_i),0\leq i<n\}$

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

同样的,我们考虑用分治方法来完成。
$$
X_0=\{x_i,0\leq i<\frac{n}{2}\}\\
X_1=\{x_i,\frac{n}{2}\leq i<n\}
$$
假设我们已经求出$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<n\}$这几个值来插值递归求出$A_1(x)$

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

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

发表评论

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