算法

FFT 即快速傅立叶变换。

多项式

表达方式

简介

  • 系数表达式,即\(f(x)=a_1x^{n-1}+a_2x^{n-2}+a_3x^{n-3}+\cdots +a_{n}\)。
  • 坐标形式。每一个坐标用\((x_i,f(x_i))\)表示。显然,为了能够表示一个确定的多项式,需要\(n\)个不同的坐标来表示。

比较

  • 对于系数表示,多项式加法的时间复杂度是\(O(n)\),多项式乘法的时间复杂度是\(O(n^2)\)。
  • 对于点值表示,多项式加法的时间复杂度同样是\(O(n)\),但是乘法的时间复杂度就是\(O(2n)\)(因为多项式乘法以后最高项次数为\(2n\),我们只需要\(2n\)个坐标表示)。

思考

这样一来,我们就有一个想法,多项式乘法,是不是可以利用坐标表示做多项式乘法特别快这点来优化算法。

于是需要解决的最大的问题就是,多项式两种表示方法之间的互相转换。

求值朴素做法的时间复杂度是\(O(n^2)\),即随便选取一个值带入,暴力计算。

差值朴素的做法时间复杂度是\(O(n^3)\),即根据坐标进行高斯消元。

在介绍 FFT 之前,得先学习 DFT (离散傅里叶变换)算法。

DFT

由于对一个多项式的点值表达式的取是任意的,所以好的取法可能会使一个算法产生本质性的蜕变。

我们选取\(n\)次单位复根作为\(x\)来取值。

单位复根

\(z^n=1(n=1,2,3,\cdots)\),这个方程的复数根\(z\)为\(n\)次单位根。

单位的\(n\)个单位根分别为\(x_k=e^{\frac{2\pi ki}{n}}(k=0,1,2,\cdots ,n-1)\)。

\(n\)个单位根在复平面的坐标表示为\((cos(\frac{2\pi k}{n}),sin(\frac{2\pi k}{n}))\),我们将这个记为\(w_{n}^{k}\)。在复平面上形象的表示的话,就是下图:

单位根在多项式的应用

我们将\(n\)个单位根带入多项式可以得到\(n\)个因变量结果,记为\(y_k\)。

我们将\(n\)个单位根的倒数\(w_{n}^{-k}\)作为自变量带入由\(y_k\)作为系数的多项式,可以得到\(z_k=\sum _{i=0}^{n-1}y_i(w_{n}^{k-1})^i\\=\sum _{i=0}^{n-1}(\sum _{j=0}^{n-1} a_j(w_{n}^{i})^j)(w_{n}^{-k})^i\\=\sum _{j=0}^{n-1}a_j(\sum _{i=0}^{n-1}(w_n^{j-k})^i)\)。

而\(\sum _{i=0}^{n-1}(w_n^{j-k})^i\)当\(j-k=0\)的时候,它为\(n\),其余时候,它为\(0\)(通过等比数列求和)。于是有\(a_i=\frac{z_i}{n}\)。

于是可以发现,将\(n\)个单位根的倒数带入变换后的多项式,可以得到原来的多项式。

这样一来,我们利用\(n\)个单位根的性质,完成了多项式两种表示方式之间的转换。

DFT算法

有了\(x_k\)的取值,我们就可以得到\(y_k\)的取值了。

\(y_k=f(x_k)=\sum _{i=0}^{n-1}a_ix_k\)。

直接暴力计算,两个方向转换的时间复杂均为\(O(n^2)\)。

FFT

那么 FFT 算法是如何优化计算这一过程的?利用分治。

我们把一个多项式的计算分为偶数项的计算和奇数项的计算:

\(f(x)=xf_{odd}(x^2)+f_{even}(x^2)\)

\(f_{odd}(x)=a_1+a_3x+\cdots +a_{n-1}x^{\frac{n}{2}-1}\)

\(f_{even}(x)=a_0+a_2x+\cdots +a_{n-2}x^{\frac{n}{2}-1}\)

也就是说, FFT 的思想就是不断得把一个多项式拆分成奇数多项式和偶数多项式,然后合并两个多项式的信息。

也就是说,如果我们已经得到了\(f_{odd}\)和\(f_{even}\),我们只需要\(O(n)\)就可以得到\(f(x)\)了。

每次都能把多项式的长度减小一半,于是时间复杂度就是\(O(nlogn)\)。

模版

C++ 是自带了复数 stl 的。

但是常数大,跑得慢,不如自己重载的好。

  • 下面的模版必须要保证\(n\)是\(2\)的整数次幂。

例题

EOJ3007】A * B II

大整数相乘。

把每一位都看成是多项式其中一项的系数,那么大数最后的结果也就是多项式乘法系数的结果。

要进位处理。

HNOI2017】礼物

【Hnoi2017】礼物

 


发表评论

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