【UOJ34】多项式乘法

uoj模板题库T1

传说中的快速傅里叶变换

以前在算法导论上看了几眼然后放弃了。。

不过静下心来读。。加上问了李学霸关于\(n\)次单位复数根的事情，大概\(40\)分钟搞定

然后代码实现就是蒯算法导论和hzwer犇的事了。。理解了还是很好码的

————————————-开始讲课————————————-

一、多项式乘法

给出两个多项式\(A=\sum_{i=0}^n a_i x^i,B=\sum_{i=0}^m b_i x^i\)

求\(A\times B\)

朴素的方法就是各位相乘，复杂度\(O(nm)\)。有没有更快的方法呢？

首先介绍一下多项式的点值表示法：

对于一个多项式\(A=\sum_{i=0}^n a_i x^i\)

取\(n\)个不同的\(x\)值，算出\(n\)个不同的\(y\)值，得到\(n\)个点\((x_1,y_1),(x_2,y_2)…\)这些点唯一确定了多项式\(A\)。用霍纳算法可以在\(O(n^2)\)的复杂度内得到一个多项式的点值表示。由系数表示法转为点值表示法的过程称为求值；其逆过程称为插值。

而点值表示法的好处为：取同样的x求值，多项式乘法的复杂度为\(O(n)\)：只要将两个多项式的\(y\)相乘即可。

则多项式乘法的过程可以转换为：对\(A\)，\(B\)求值->点值乘法->插值

若能将求值和插值的复杂度降低，就能达到我们的目的了！

二、FFT

【【声明：以下规定\(n\)为\(2\)的幂】】【你问我\(n\)不是\(2\)的幂怎么办？扩大一下，高位系数全为\(0\)不就完了

FFT的核心思想：通过恰当选取\(x\)的值，并采用分治策略使得求值和插值的复杂度降为\(O(nlogn)\)。

首先我们要了解的是\(n\)次单位复数根（%数学组李浚鼎大薛霸）

\(n\)次单位复数根：表示为\(ω_n，ω_n^n=1\)

并且\(n\)次单位复数根的个数为\(n\)

算法导论告诉我们，\(n\)个单位复数根均匀的分布在以复平面的原点为圆心的单位半径的圆周上

再举个例子。。\(4\)次单位复数根就是\(±1\)和复数中喜闻乐见的\(±i\)

那么究竟怎么求呢

有公式\(ω_n^k=e^{2πi\frac{k}{n}}\)

然后又根据\(e^{iu}=cos(u)+isin(u)\)

于是\(ω_n^k=cos(2πk/n)+isin(2πk/n)\)

代码就好写了是吧

那么这玩意有什么用呢？

再给出两个引理：

消去引理：\(ω_{ak}^{bk}=e^{2πi\frac{bk}{ak}}=e^{2πi\frac{b}{a}}=ω_a^b\)

折半引理：由消去引理易证，如果\(n\)为大于\(0\)的偶数，那么\(ω_n\)平方的集合为\(ω_{n/2}\)的集合

即，\(ω_n\)平方的集合中元素的个数仅为\(\frac{n}{2}\)

故可以进行分治

将\(A=\sum_{i=0}^n a_i x^i\)拆分为

\(A_0={a_0,a_2x,a_4x^2,…,a_{n-2}^{n/2-1}}\)（所有下标二进制末尾为\(0\)的系数组成的多项式）

\(A_1={a_1,a_3x,a_5x^2,…,a_{n-1}^{n/2-1}}\)（所有下标二进制末尾为\(1\)的系数组成的多项式）

则\(A(x)=A_0(x^2)+xA_1(x^2)\)

那么若我们代入A的各个x值为n个n次单位复数根。。则\(x^2\)的取值仅有\(\frac{n}{2}\)个。。

那么两个子问题\(A_0(x^2),A_1(x^2)\)的规模都只有原问题的一半。。

Congratulations! 复杂度已经被我们降到了\(O((n+m)log(n+m))\)。

至于插值，只要将\(ω_n变成ω_n^{-1}\)，再将所得结果都除以\(n\)即可，证明见算法导论。

于是我们得到了递归代码：

其中核心的FFT函数也只有\(9\)行呢。。有点不可思议的感觉

这样我们就能够AC了，总时间将近\(4\)秒的样子

但是！我们要精益求精是不是！

既然是这么simple的递归就肯定能转成非递归版本的，常数更小对不对！

那我们来分析一下这个递归的结构：

我们只要把原数组先排成最底下一排的顺序再两两合并就可以自底向上地实现了

那么观察一下最后一排的顺序：发现把每一个二进制数前后颠倒即为原数组

那么就很简单了（详见代码）