Warning


由于本博客作者实在是太弱啦,本篇文章可能存在大量的错误,漏洞,不规范,不合法之处。若您发现本文章所存在的任何问题,请您尽快在评论区指出,十分感谢!

updata 2017/9/12


这个坑填了一下 Fa♂Fa♂T ,ppt 是口胡的,里面好像有点小错误,懒得改了 T.T。过一阵子会搬过来。

问题


给出两个多项式 A 和 B,求它们的乘积. 记 n,m 分别为 A,B 的次数.

n,m≤106

暴力


$$系数表达式 A B \overset{O(n^{2})}{\rightarrow} 系数表达式 X$$

我们令 X 为答案多项式,很容易地,我们有一个 n2 的做法,通过下式对 X 的每一项系数暴力求和

$$X_n=\sum_{i=0}^{n}a_i\times b_i$$

但是这并不能满足数据范围的要求. 但这可以给我们思路上的启发,我所需要做的就是 直接计算答案的每一位

我们考虑换一种方法。

点值表达式


对于一个多项式 A,我们常常这样表达它:$$A=a_0*x^0+a_1*x^1+...+a_n*x^n$$

事实上,这种习惯做法我们称之为系数表达式,它有很多优点,比如方便在 O(n) 的时间内求出对于任意一个 x,该多项式的值,但它有一个显而易见的缺陷:系数表达式间的运算的复杂度是无法接受的。

所有我们有另外一种具有良好性质的表达多项式的方法——点值表达式。

对于一个二次多项式函数 ,如果给定它图像所经过的 3 个互异的点,我们就可以求出它的系数表达式,事实上,对于一个 n 次多项式,只要给定 n+1 个互异的点,我们就可以将它唯一确定. 至于如何确定,通过 高斯消元拉格朗日插值法 便可以做到。

所以我们就有了一种全新的多项式表达方式:点值表达。例如多项式 x2,(0,0),(1,2)(2,4). 就是它的一种点值表达,显然的,一个多项式有无数种点值表达.

那么点值表达式有什么优越的性质呢?

考虑多项式加法 A+B,答案多项式 X 很显然是一个 max(n,m) 次的多项式,也就是说,我们可以用 max(n,m)+1 个点唯一确定它. 而这些点可以通过 A 和 B 的点值表达得到,如果我们取 x 值相同的点:

A:(x1,ya1),(x2,ya2)⋯
B:(x1,yb1),(x2,yb2)⋯

那么 X 的点值表达式就是这样的:X:(x1,ya1+yb1),(x2,ya2+yb2)⋯

正确性通过图像便可以理解:

同时,对于多项式乘法 A*B,同样可以这样计算,那么答案 X 多项式便可以这样表示...

X:(x1,ya1*yb1),(x2,ya2*yb2)⋯

这样,多项式乘法的复杂度就被降到了 O(n) !

$$点值表达式 A B \overset{O(n)}{\rightarrow} 点值表达式 X$$

由于点值表达式良好的性质,我们可以考虑通过点值表达式间接完成系数表达式的相乘,即:

$$系数表达式 A B\overset{DFT}{\rightarrow} 点值表达式 A B \overset{O(n)}{\rightarrow} 点值表达式 X\overset{IDFT}{\rightarrow} 系数表达式 X$$

通常,我们采用 DFT(离散傅里叶变换)计算点值表达式,IDFT 表示其逆运算.

然而,朴素的做法是对于每一个点,均 O(n) 的求一遍值,然而如果这么做,复杂度又退化到了 O(n2)... 所以我们需要 FFT 优化 DFT 的过程!

单位复数根


我们注意到,在求点值表达式时,x 值是可以任意选择的,所以我们可以考虑选取一些具有特殊性质的 x 值以尝试优化复杂度,单位复数根就是我们的选择。

我们以\(ω_n^{k}\) 来表示 n 的 k 次复根,通过几何意义理解它是比较容易的,它以分布在以 (0,0) 为中心的复平面圆上

当 n=8 时,如下图

它具有如下的性质,根据图像脑补是很容易的...

$$ω_{n}^{n}=ω_{n}^{0}=1$$

$$ω_{dn}^{dk}=ω_{n}^{k}   (消去引理)$$

$$(ω_{n}^{k})^{2}=ω_{n/2}^{k}   (折半引理)$$

另外... 欧拉告诉我们

$$ω_{n}^{k}=cos(2\pi k/n)+isin(2\pi k/n)$$

还可以从图像看出... 对于\(ω_n^{k}\) ,尽管它有 n 种取值... 它的平方只有 n/2 种取值....

因为它具有这样那样的性质... 所以采取它作为 x 坐标求值

FFT(快速傅里叶变换)


FFT 最常见的算法就是 Cooley-Tukey 算法了... 它是基于分治策略的。

算了还是未完待续吧


一个非常弱的准退役OIER