多项式算法

Published: by Creative Commons Licence

  • Tags:

快速数论变换

了解快速傅里叶变换的人应该知道,快速傅里叶变换之所以能成立源于对任意正整数n,存在这样的一个单位根$w(n)$,满足四个条件:

  1. $w(n)^0,w(n)^1, \ldots, w(n)^{n-1}$各不相同
  2. $w(n)^n = 1$
  3. $w(dn)^{dk}=w(n)^k$。
  4. $w(2n)^n=-1$

在快速傅里叶变换中,我们选取$w(n)=e^{(2\pi /n)i}$作为单位根。

快速傅里叶变换会存在一定的精度损失问题,我们可以使用快速数论变换来替代。但是快速数论变换实际上还是沿用了快速傅里叶变换的整体框架,只是替换了单位根。我们需要找一个素数p,并找到它的一个原根g。可以发现当我们取$w(n)=g^{\frac{p-1}{n}}$时,可以满足上面所有条件。不是所有p都适合用于快速数论变换,我们需要找一个比较特殊的p,使得$n|p-1$。由于n一般是2的幂次,因此我们希望$p-1$包含尽可能多的因子2,下面介绍两个常用的选择:

剩下的和快速傅里叶变换没有什么区别,直接套用就好了。

卷积精度溢出

快速傅里叶变换可能会遇到乘积的系数超过浮点数精度,而快速数论变换也存在系数超出模素数,导致与真实结果出现不同。

容易发现,如果两个多项式最大系数为m,而多项式的长度为n,那么卷积后结果的最大系数不会超过$m^2n$。

我们先假设所有系数都是整数(如果浮点数,那么就除去最小精度EPS,之后取整)。一种简单的思路是,我们可以将两个多项式进行处理,选择一个k,记$a%k$表示将a的系数都模上k得到的多项式,$a/k$表示将a的系数都下整除k得到的多项式。那么

这样就可以减小每一次卷积得到系数的大小。从而避免溢出问题。

还有一种方案就是将多项式拆成两个,这时候我们只需要记$a/k$表示多项式a的后k项的系数为0的多项式,而$a%k$表示多项式a仅后k项不变,其它项系数均变为0的多项式。可以得出:

多项式求逆

给出多项式A,找到A的逆多项式B,满足$AB=1\mod x^n$。

当n为1时,问题非常简单,此时A的逆多项式一定是$1/A[0]$。假设我们已经找到了某个多项式C,使得$AC=1\mod x^{n/2}$。那么,可以推导出:

最后一步需要说明下,对于$B-C$的后n项都是0,因此对于$B-C$的$x^i$的系数,若$i<n/2$,那么系数一定是$B-C$的后$n/2$项中两项的乘积的累加,一定是0,若$i\geq n/2$,那么一定是后$n/2$项和前$n/2$项的系数乘积的累和,也是0。

将二次方程展开:

之后两端都乘上A,借助$AB=1$可知:

这样我们就得到了多项式B,并且可以发现,整个流程我们仅假设$A[0]$可逆,即一个多项式可逆当且仅当其$x^0$项的系数可逆。

多项式求逆的时间复杂度为$T(n)=T(\frac{n}{2})+\alpha n\log_2n=O(2\alpha n\log_2n)=O(n\log_2n)$,其中$\alpha$是固定常数。

多项式除法取模

我的天哪,多项式可以有除法了。。。

对于阶数为n的多项式$f(x)$,记$f^R(x)=x^nf(\frac{1}{x})$,换句话说$f^R(x)$是$f(x)$的系数前后交换后得到的。

接下来考虑阶数为$n$的多项式$A$和阶数为$m$的多项式$B$,以及阶数小于$m$的多项式$R$,我们希望得到如下形式等式$A(x)=B(x)C(x)+R(x)$。推一下公式:

最后的结果可以通过对多项式求逆得到。

而取模可以通过$R(x)=A(x)-B(x)C(x)$得到。

多项式除法和取模都仅涉及到一次的多项式求逆和乘法,因此时间复杂度为$O(n\log_2n)$。

多项式多点求值

给出$n$阶多项式$f$,以及$m$个不同的数$x_1,\ldots, x_m$,要求计算$f(x_1),\ldots,f(x_m)$。

很显然可以设计一套暴力算法,$O(nm)$时间复杂度解决。但是这个问题存在丧心病狂的$O(n\log_2n+m(\log_2m)^2)$的解法。

我们可以$m$个数值分成相同大小的两部分。第一部分是$X_1={x_1,\ldots,x_{\frac{m}{2}}}$,第二部分是$X_2={x_{\frac{m}{2}+1},\ldots, x_m}$。

之后我们定义$g(x)=\prod_{i=1}^{\frac{m}{2}} (x-x_i)$,很显然对于任意$x'\in X_1$,满足$g(x')=0$。我们利用多项式除法可以得到:$f(x)=g(x)A(x)+R(x)$,其中$R$的阶数小于$\frac{m}{2}$。利用$x'\in X_1 \Rightarrow f(x')=R(x')$,因此我们现在只需要计算$X_1$在某个不超过$m$阶的多项式下的取值。重复这个过程,直到点集不可再分。

分治的时间复杂度为:

总的时间复杂度为$O(n\log_2n+m(\log_2m)^2)$。

提供一道题目(卡常SB题,慎做)。

等差卷积

考虑计算下面多项式:

它非常类似于一般卷积,只是内部是等差,而一般卷积是等和。我们定义$f'(x)=f(n-x)$。那么代入得到

很显然$H'$可以利用一般的快速卷积在$O(n\log_2n)$时间复杂度内得到,下面我们来看$H'$和$H$的关系。

这里包含了所有差为$n-i$的项的和。因此可以得到:

即最终我们可以通过翻转$H'$得到$H$。

注意这里我们要在$f$前面填充0之前翻转,且$H'$也仅翻转后面的$n$项目。

求序列等幂和

假设提供一个序列${a_i}$,记$f(k)=\sum_{i=1}^na_i^k$,要求我们计算出$f(1),f(2),\ldots, f(m)$。

这个问题可以用生成函数$G(x)$来求解。

假如我们记$D(x)=\prod_{j}(1-a_jx)$,记$U(x)=\sum_{j=1}^n\prod_{j\neq i}(1-a_jx)$,那么我们可以发现$D_i$和$U_i$存在某种联系。事实上,考虑所有对$x^j$有贡献的系数一定是$j$个${-a_i}$序列中的数的乘积,而这个乘积会在$U_i$中出现贡献$n-j$次。因此我们可以直接断定$U_i=(n-i)D_i$。

于是乎我们得到了$U(x)$和$D(x)$后,就可以用多项式求逆的技术得出$G(x)=U(x)D^{-1}(x)$。

这里我们计算$D(x)$的时候,可以利用分治+快速卷积的技术将时间复杂度优化到$O(n(\log_2n)^2 )$。

多项式差与多项式前缀和

定义1:对于一个任意多项式$f(x)$,我们记其前缀和函数为$g(x)=\sum_{i=0}^xf(i)$。

命题1:对于任意$n$阶多项式$A(x)$,我们始终可以找到另外一个$n+1$阶多项式$B(x)$,满足$B(x)-B(x-1)=A(x)$

证明:

我们可以利用归纳法进行证明,当$A(x)$是0阶多项式的时候,即$A(x)=c$,那么我们可以得到$B(x)=cx$,很显然$B(x)-B(x-1)=cx-c(x-1)=c=A(x)$。

假设对于任意不大于$k-1$阶的多项式$A(x)$,命题都成立,那么当$A(x)$为$k$阶多项式的时候,记$A(x)=a_kx^k+\ldots+a_0$,注意到$x^k-(x-1)^k$是$k-1$阶多项式,因此我们可以通过为$B(x)$选择合适的最高项系数$b_{k+1}=\frac{a_k}{k}$,将问题化简为$(B(x)-b_{k+1}x^{k+1})-(B(x-1)-b_{k+1}(x-1)^{k+1})=A(x)-(b_{k+1}x^{k+1}-b_{k+1}(x-1)^{k+1})$,我们重新标记后得到公式:$B'(x)-B'(x-1)=A'(x)$,其中我们要找的$B'(x)$是$k$阶多项式,而$A'(x)$是$k-1$阶多项式,而之前的归纳法已经证明了$B'(x)$的存在性,因此$B(x)=B'(x)+b_{k+1}x^{k+1}$也是存在的。

命题2:如果多项式$f(x)$是$n$阶多项式,那么其前缀和函数$g(x)$一定是$n+1$阶多项式

证明:

首先注意到$g(x)-g(x-1)=f(x)$,按照命题1我们一定可以刻画出这样一个$n+1$阶多项式$g(x)$,现在只需要保证$g(0)=f(0)$即可。注意到修改$g(x)$的常数项不会影响$g(x)-g(x-1)=f(x)$等式的成立,因此我们可以通过修改$g(x)$的常数项为$f(0)$即可找到与前缀和函数完全相同的一个$n+1$阶多项式。

多项式牛顿迭代

本段基本照搬OIWIKI上的内容

给定多项式$g(x)$,已知有$f(x)$满足

求出模$x^n$意义下的$f(x)$。

当$n=1$的时候,自行计算满足$g(f(x))=0\mod x^n$的多项式$f(x)$。

假设已经得到了模$x^{\lceil\frac{n}{2}\rceil}$意义下的解$f_0(x)$,现在要求模$x^n$意义下的解$f(x)$。可以将$g(f(x))$在$f_0(x)$处泰勒展开(真的可以这么做吗??我的微积分看来要重新学了),有:

这里由于$f(x)-f_0(x)$的最低非零项系数最低为$\lceil\frac{n}{2}\rceil$,故有:

因此可以简化泰勒展开公式:

参考资料