Difficulty：5.0 / Template
题意解析：给定两个多项式，求它们的积。
假设积的次数为 n−1n-1n−1，其中 nnn 为 222 的正整数次幂。如果不是的话补成二的正整数次幂就行。
朴素方法是直接枚举两个多项式的每一项，乘起来。但这样的话是 O(n2)O(n^2)O(n2) 的，太慢了。
注意到有一个定理：nnn 个不同的值可以表示出唯一一个不超过 n−1n-1n−1 项式。所以考虑一种神秘的方法：取 nnn 个不同的值分别代入多项式，然后将两个多项式的值乘起来，再用某种方法还原出乘积。
例如两个多项式分别为 x+1x+1x+1 与 x−2x-2x−2，我们取一些值分别代入：
* x=1→x+1=2,x−2=−1,(x+1)(x−2)=−2x=1\rarr x+1=2,x-2=-1,(x+1)(x-2)=-2x=1→x+1=2,x−2=−1,(x+1)(x−2)=−2。
* x=2→x+1=3,x−2=0,(x+1)(x−2)=0x=2\rarr x+1=3,x-2=0,(x+1)(x-2)=0x=2→x+1=3,x−2=0,(x+1)(x−2)=0。
* x=3→x+1=4,x−2=1,(x+1)(x−2)=4x=3\rarr x+1=4,x-2=1,(x+1)(x-2)=4x=3→x+1=4,x−2=1,(x+1)(x−2)=4。
对于 (1,−2),(2,0),(3,4)(1,-2),(2,0),(3,4)(1,−2),(2,0),(3,4) 进行求解，解得多项式为 x2−x−2x^2-x-2x2−x−2。
但我们发现，如果只是代入整数的话，解起来十分困难。
考虑复数领域的单位根 ωn=cos(2πn)+isin(2πn)\omega_n=\cos (\frac{2\pi}{n})+i\sin(\frac{2\pi}{n})ωn =cos(n2π )+isin(n2π )。
这个单位根其实就是 111 逆时针旋转了 1n×360°\frac{1}{n}\times 360\degreen1 ×360°。
这玩意有个性质，就是乘几次方就旋转几倍的度数，也就是说 ωnk\omega_n^kωnk 是 111 逆时针旋转 kn×360°\frac{k}{n}\times 360\degreenk ×360°。ωn0=ωnn=1\omega_{n}^{0}=\omega_{n}^n=1ωn0 =ωnn =1。
那这个性质有什么用呢？我们可以发现通过单位根，可以很方便地逆向推导出原数组！
假设 f(x)=∑i=0n−1aixif(x)=\sum_{i=0}^{n-1} a_ix^if(x)=∑i=0n−1 ai xi ，代入后的点是 (ωn0,y0),(ωn1,y1),...,(ωnn−1,yn−1)(\omega_{n}^0,y_0),(\omega_n^1,y_1),...,(\omega_n^{n-1},y_{n-1})(ωn0 ,y0 ),(ωn1 ,y1 ),...,(ωnn−1 ,yn−1 ) 。
记多项式 f′(x)=∑i=0n−1yixif'(x)=\sum_{i=0}^{n-1} y_ix^if′(x)=∑i=0n−1 yi xi。
我们把单位根分别的倒数 ωnn,ωnn−1,...,ωn1\omega_n^{n},\omega_n^{n-1},...,\omega_n^1ωnn ,ωnn−1 ,...,ωn1 依次代入，得
(ωnn,z0),(ωnn−1,z1),...,(ωn1,zn−1)(\omega_{n}^{n},z_0),(\omega_n^{n-1},z_1),...,(\omega_n^1,z_{n-1})(ωnn ,z0 ),(ωnn−1 ,z1 ),...,(ωn1 ,zn−1 )。
此时有
zk=∑i=0n−1yiωn−i×k=∑i=0n−1(∑j=0n−1aj×ωni×j×ωni×(−k))=∑i=0n−1aj×(∑j=0n−1ωni×(j−k))z_k\\ =\sum_{i=0}^{n-1}y_i\omega_n^{-i\times k}\\ =\sum_{i=0}^{n-1}(\sum_{j=0}^{n-1}a_j\times \omega_n^{i\times j}\times \omega_n^{i\times (-k)})\\ =\sum_{i=0}^{n-1}a_j\times (\sum_{j=0}^{n-1}\omega_n^{i\times (j-k)})
zk =i=0∑n−1 yi ωn−i×k =i=0∑n−1 (j=0∑n−1 aj ×ωni×j ×ωni×(−k) )=i=0∑n−1 aj ×(j=0∑n−1 ωni×(j−k) )
当 j=kj=kj=k 时，里面那一项是 nnn，否则由等比数列求和可知里面那一项是 000。
所以此时 zk=n×akz_k=n\times a_kzk =n×ak 。
我们只需要把每一项 zkz_kzk 求出来，除以 nnn 就能还原出 f(x)f(x)f(x) 了。
但此时还是 O(n2)O(n^2)O(n2) 的。
下周写吧。
