学习：多项式算法----FFT
FFT，即快速傅里葉變換，是離散傅里葉變換的快速方法，可以在很低復(fù)雜度內(nèi)解決多項(xiàng)式乘積的問題（兩個(gè)序列的卷積）
?
卷積
?
卷積通俗來說就一個(gè)公式（本人覺得卷積不重要）
$$C_k=\sum_{i+j=k}A_i*B_i$$
?那么這個(gè)表達(dá)式是啥意思了：
有兩個(gè)序列A和B，其中$A=\left\{A_1,A_2,...\right\}，B=\left\{B_1,B_2,...\right\}$
A序列有a個(gè)元素，B序列有b個(gè)元素。于是，由這兩個(gè)序列可以推出另一個(gè)序列C，C序列如何確定了？確定方法就按照卷積的公式得來的，即$$C=\left\{\sum_{i+k=0}A_i*B_j\,,\,\sum_{i+k=1}A_i*B_j\,,...,\sum_{i+k=2^a+2^b}A_i*B_j\right\}$$
?
這里只介紹一下卷積，下面來探究卷積和多項(xiàng)式之間的關(guān)系。
?
?
?
多項(xiàng)式（預(yù)備知識(shí)）
?
多項(xiàng)式的定義
形如
$$f(x)=a_0+a_1x+a_2x^2+...+a_nx^n$$
的函數(shù)關(guān)系式叫做關(guān)于x的多項(xiàng)式，其中多項(xiàng)式系數(shù)可以構(gòu)成一個(gè)序列，即
$$A=\left\{a_0,a_1,a_2,...,a_n\right\}$$
?
?
多項(xiàng)式乘法與序列的卷積
假如有兩個(gè)多項(xiàng)式，其中
$f(x)=a_0+a_1x+a_2x^2+...+a_nx^n$
$g(x)=b_0+b_1x+b_2x^2+...+b_mx^m$
?
現(xiàn)在要求f(x)*g(x)的序列，很明顯
$$f(x)*g(x)=\sum_{i+j=0}a_i*b_j+\sum_{i+j=1}a_i*b_jx+\sum_{i+j=2}a_i*b_jx^2+...+\sum_{i+j=m+n}a_i*b_jx^{m+n}$$
?
現(xiàn)在把$f(x),g(x)$以及$f(x)*g(x)$三個(gè)多項(xiàng)式的系數(shù)拿出來寫成三個(gè)序列，可得:
$A=\left\{a_0,a_1,a_2,...a_n\right\}$
$B=\left\{b_0,b_1,b_2,...b_m\right\}$
$C=\left\{\sum_{i+j=0}a_i*b_j,\sum_{i+j=1}a_i*b_j,\sum_{i+j=2}a_i*b_j,...\sum_{i+j=m+n}a_i*b_j\right\}$
?
于是驚訝的發(fā)現(xiàn)，兩個(gè)序列的卷積相當(dāng)于兩個(gè)多項(xiàng)式乘積后得到的多項(xiàng)式的系數(shù)序列。而FFT算法的目的，就是求兩個(gè)多項(xiàng)式乘積后得到的多項(xiàng)式的系數(shù)序列。
?
?
多項(xiàng)式的表示方法
多項(xiàng)式有兩種表示方法，即系數(shù)表示法和點(diǎn)值表示法。
?
1.系數(shù)表示法是我們常用的表示方法，即
$$f(x)=a_0+a_1x+a_2x^2+...+a_nx^n$$
的形式
?
2.點(diǎn)值表示法，顧名思義，就是在這個(gè)多項(xiàng)式上任意選取不重復(fù)的n+1個(gè)點(diǎn)，即
$$f(x)=\left\{(x_0,y_0),(x_1,y_1),...,(x_2,y_2)\right\}$$
可以證明：任何n+1個(gè)點(diǎn)可以確定唯一一個(gè)最高次項(xiàng)為n次方的多項(xiàng)式（下面是證明，可以看看，也可以忽略）
將一個(gè)多項(xiàng)式的系數(shù)寫成一個(gè)系數(shù)矩陣（當(dāng)然，這些系數(shù)我們是不知道的）
$$\begin{bmatrix}a_0\\a_1\\a_2\\\vdots\\a_n\end{bmatrix}$$
然后將剛剛選取的n+1個(gè)點(diǎn)寫成下面兩個(gè)矩陣
$$\begin{bmatrix}1&x_0&x_0^2&x_0^3&\cdots&x_0^n\\1&x_1&x_1^2&x_1^3&\cdots&x_1^n\\1&x_2&x_2^2&x_2^3&\cdots&x_2^n\\\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\1&x_n&x_n^2&x_n^3&\cdots&x_n^n\end{bmatrix}\;\begin{bmatrix}y_0\\y_1\\y_2\\\vdots\\y_n\end{bmatrix}$$
可以得出以下三個(gè)矩陣的關(guān)系
$$\begin{bmatrix}1&x_0&x_0^2&x_0^3&\cdots&x_0^n\\1&x_1&x_1^2&x_1^3&\cdots&x_1^n\\1&x_2&x_2^2&x_2^3&\cdots&x_2^n\\\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\1&x_n&x_n^2&x_n^3&\cdots&x_n^n\end{bmatrix}\;\begin{bmatrix}a_0\\a_1\\a_2\\\vdots\\a_n\end{bmatrix}=\begin{bmatrix}y_0\\y_1\\y_2\\\vdots\\y_n\end{bmatrix}$$
解出系數(shù)矩陣
$$\begin{bmatrix}a_0\\a_1\\a_2\\\vdots\\a_n\end{bmatrix}=\begin{bmatrix}1&x_0&x_0^2&x_0^3&\cdots&x_0^n\\1&x_1&x_1^2&x_1^3&\cdots&x_1^n\\1&x_2&x_2^2&x_2^3&\cdots&x_2^n\\\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\1&x_n&x_n^2&x_n^3&\cdots&x_n^n\end{bmatrix}^{-1}\begin{bmatrix}y_0\\y_1\\y_2\\\vdots\\y_n\end{bmatrix}$$
只能唯一確定一個(gè)系數(shù)矩陣，即只能唯一確定一組系數(shù)，即只能唯一確定一個(gè)多項(xiàng)式，證明完畢
?
?
多項(xiàng)式乘法與FFT算法
為了實(shí)現(xiàn)多項(xiàng)式乘法并得到系數(shù)序列，我們可以考慮實(shí)現(xiàn)的方法，如果直接暴力（通過定義直接算系數(shù)）是O(n2)復(fù)雜度，肯定會(huì)超時(shí)，于是我們這樣考慮
?
首先可以選取n+1個(gè)點(diǎn)，把兩個(gè)多項(xiàng)式轉(zhuǎn)化為點(diǎn)值表示法。
?
然后將兩個(gè)點(diǎn)值表示法的多項(xiàng)式相乘（復(fù)雜度為O(n)）,然后將新得到的多項(xiàng)式的點(diǎn)值表示法轉(zhuǎn)化為系數(shù)表示法。
?
注意：假設(shè)f(x)最高有n次方，g(x)最高有m次方，所以f(x)*g(x)最高有m+n次方，但是m+n可能不是2的冪次方，如果不是，則需要選取點(diǎn)的數(shù)量應(yīng)該是大于m+n的2的冪次方個(gè)，假設(shè)這個(gè)值為1<<k，所以從系數(shù)表示法到點(diǎn)值表示法的轉(zhuǎn)化過程中，我們要在f(x)和g(x)內(nèi)選擇1<<k的點(diǎn)，才能保證點(diǎn)值表示法的f(x)和g(x)之后，至少仍有m+n個(gè)點(diǎn)，才能確定唯一一個(gè)f(x)*g(x)的多項(xiàng)式。所以在選取點(diǎn)的數(shù)量的時(shí)候，要保證點(diǎn)的個(gè)數(shù)能確定f(x)*g(x)后的多項(xiàng)式。
?
如果任意的選取n+m個(gè)點(diǎn)然后轉(zhuǎn)化，復(fù)雜度還是太高，所以我們需要巧妙的選取1<<k個(gè)點(diǎn)，從而使得系數(shù)表示法與點(diǎn)值表示法之間轉(zhuǎn)化的復(fù)雜度降為O(nlogn)，這就是FFT算法。
?
?
?
虛數(shù)的乘積及其表示（預(yù)備知識(shí)）
?
一個(gè)虛數(shù)，是由實(shí)部和虛部組成，表示為$(a+bi)$，虛數(shù)的幾何表示可以在坐標(biāo)系中體現(xiàn)，如下圖所示
?
如圖所示，$r$為此虛數(shù)的模長(zhǎng)，$\theta$為此虛數(shù)的幅角，于是虛數(shù)還能表示為$r(cos\theta,isin\theta)$的形式
?
若$z_1=r_1(cos\theta_1,isin\theta_1),z_2=r_2(cos\theta_2,isin\theta_2)$
于是$$z_1*z_2=r_1(cos\theta_1,isin\theta_1)*r_2(cos\theta_2,isin\theta_2)=r_1r_2(cos(\theta_1+\theta_2),isin(\theta_1+\theta_2))$$
?
可以得到虛數(shù)相乘的幾何意義：模長(zhǎng)相乘，幅角相加
?
?
?
n次單位根（預(yù)備知識(shí)）
?
定義
n次單位根$w_n$，即$x^n=1$在虛數(shù)范圍內(nèi)的解，即$w_n^n=1$，故n次單位根$w_n$也是一個(gè)復(fù)數(shù)，且模長(zhǎng)為1，所以n次單位根在乘方的時(shí)候模長(zhǎng)不變，幅角等差增大
?
如圖所示，將一個(gè)單位圓分成n塊，幅角為正且最小的那個(gè)虛數(shù)即為n次單位根（$w_n^1$，紅色點(diǎn)），下圖是n=8的情況
還要注意，$w_n^0=w_n^n=1$
由圖及n次單位根的性質(zhì)（n次單位根模長(zhǎng)為1，幅角為$\frac{2\pi}{n}$）可得
$$w_n^k=cos\frac{2k\pi}{n}+i\,sin\frac{2k\pi}{n}$$
?
?
性質(zhì)
比較簡(jiǎn)單的性質(zhì)：
1.$w_n^{m+n}=w_n^m*w_n^n=w_n^m$
2.$(w_n^m)^n=(w_n^n)^m=1,m\in [0,n-1]$
?
比較復(fù)雜（重要）的性質(zhì)：
1.$w_{2n}^{2k}=w_n^k$，如圖所示
2.$w_n^k=-w_n^{k+\frac n{2}}$
通過上面那個(gè)圖也可以看出來，注意一點(diǎn)：虛數(shù)乘-1，那么虛數(shù)的實(shí)部與虛部都要乘上-1，所以$-w_n^k$在單位圓上的點(diǎn)和$w_n^k$在單位圓上的點(diǎn)關(guān)于原點(diǎn)對(duì)稱
3.$(w_n^k)^2=w_{\frac n{2}}^k$
推導(dǎo):$(w_n^k)^2=(-w_n^{k+\frac n{2}})^2=w_n^{2*k}=w_{\frac n{2}}^k$
?
更加復(fù)雜（重要）的性質(zhì)
$$\sum_{k=0}^{n-1}w_n^{ik}=\begin{cases} 0 & i\bmod n \ne 0 \\ n & i\bmod n=0 \end{cases}$$
證明：
當(dāng)$i\bmod n \ne 0$時(shí)，相當(dāng)如等比數(shù)列前n項(xiàng)和求和，故$$\sum_{k=0}^{n-1}w_n^{ik}=\frac {w_n^0(1-(w_n^i)^n)}{1-w_n^i}=\frac {1-(w_n^n)^i}{1-w_n^i}=0$$
當(dāng)$i\bmod n = 0$時(shí)，$w_n^{ik}=1$，故$$\sum_{k=0}^{n-1}w_n^{ik}=n*1=n$$
?
至此，你應(yīng)該知道，多項(xiàng)式從系數(shù)表示法轉(zhuǎn)化為點(diǎn)值表示法時(shí)，選取的n個(gè)點(diǎn)的x值即為n次單位根序列$\left\{w_n^0,w_n^1,....,w_n^{n-1}\right\}$
?
注意，此處的n是f(x)*g(x)的多項(xiàng)式最高次項(xiàng)的次數(shù)，不是f(x)或者g(x)最高此項(xiàng)的系數(shù)，前面（多項(xiàng)式乘法與FFT）講過要選取1<<k（再次強(qiáng)調(diào)這個(gè)值比f(x)*g(x)的多項(xiàng)式最高次的次數(shù)m+n還要大，且是2的冪次方）個(gè)點(diǎn)
?
?
?
FFT
?
假設(shè)現(xiàn)在多項(xiàng)式為
$f(x)=a_0+a_1x+a_2x^2+...+a_{k-1}x^{k-1}$，注意，多項(xiàng)式最高次項(xiàng)為k-1次方，共k項(xiàng)，k如果不等于2的n次冪，就湊成2的n次冪（加系數(shù)為0的項(xiàng)）
$g(x)=b_0+b_1x+b_2x^2+...+b_{h-1}x^{h-1}$，注意，多項(xiàng)式最高次項(xiàng)為h-1次方，共h項(xiàng)，h如果不等于2的n次冪，就湊成2的n次冪（加系數(shù)為0的項(xiàng)）
?
那么現(xiàn)在，我們從多項(xiàng)式中選取了這樣一些點(diǎn)
${(w_n^0,f(w_n^0)),(w_n^1,f(w_n^1)),(w_n^2,f(w_n^2)),...,(w_n^{n-1},f(w_n^{n-1}))}$，共n個(gè)點(diǎn)
注意n是大于k+h的最小2次冪，而不是等于k+h！！！！！
?
此時(shí)選取得點(diǎn)數(shù)n大于k+h，故可以確定f(x)*g(x)這個(gè)多項(xiàng)式，現(xiàn)在，只需確定$f(w_n^0),f(w_n^1),...,f(w_n^{n-1})$的值即可。
?
如何算值？我們可以觀察一下$f(w_n^i)$的值$(0\le i<n)$
$f(w_n^i)=a_0+a_1w_n^i+a_2(w_n^i)^2+a_3(w_n^i)^3+...+a_{k-1}(w_n^i)^{k-1}$
$=\color{Red}{a_0+a_2(w_n^i)^2+a_4(w_n^i)^4+...+a_{k-2}(w_n^i)^{k-2}}+\color{LimeGreen}{w_n^i}\color{Blue}{(a_1+a_3(w_n^i)^2+...+a_{k-1}(w_n^i)^{k-2})}$
根據(jù)$(w_n^k)^2=w_{\frac n{2}}^k$可得
$=\color{Red}{a_0+a_2w_{\frac n{2}}^i+a_4(w_{\frac n{2}}^i)^2+...+a_{k-2}(w_{\frac n{2}}^i)^{\frac {k-2}2}}+\color{LimeGreen}{w_n^i}\color{Blue}{(a_1+a_3w_{\frac n{2}}^i+...+a_{k-1}(w_{\frac n{2}}^i)^{\frac {k-2}2})}$
$=\color{Red}{f_1(w_n^i)}+\color{LimeGreen}{w_n^i}\color{Blue}{f_2(w_n^i)}$
?
再算$f_1(w_n^i)$的值和$f_2(w_n^i)$的值的時(shí)候，我們又可以按照奇偶分開，像算$f(w_n^i)$一樣變成兩個(gè)問題
?
同時(shí)我們發(fā)現(xiàn)
$f(w_n^{i+\frac n{2}})=f(-w_n^i)$
$=\color{Red}{a_0+a_2(-w_n^i)^2+a_4(-w_n^i)^4+...+a_{k-2}(-w_n^i)^{k-2}}-\color{LimeGreen}{w_n^i}\color{Blue}{(a_1+a_3(-w_n^i)^2+...+a_{k-1}(-w_n^i)^{k-2})}$
$=\color{Red}{a_0+a_2w_{\frac n{2}}^i+a_4(w_{\frac n{2}}^i)^2+...+a_{k-2}(w_{\frac n{2}}^i)^{\frac {k-2}2}}-\color{LimeGreen}{w_n^i}\color{Blue}{(a_1+a_3w_{\frac n{2}}^i+...+a_{k-1}(w_{\frac n{2}}^i)^{\frac {k-2}2})}$
$=\color{Red}{f_1(w_n^i)}-\color{LimeGreen}{w_n^i}\color{Blue}{f_2(w_n^i)}$
?
又發(fā)現(xiàn)，如果我們要算$f(w_n^i)$的值，我們會(huì)先算$f_1(w_n^i)$和$f_2(w_n^i)$的值，但是算出$f_1(w_n^i)$和$f_2(w_n^i)$的值之后，不僅能算出$f(w_n^i)$的值，還能同時(shí)算出$f(w_n^{i+\frac n{2}})$的值
?
總的來說，如果n=8算出了$f(w_n^0)$的值，就算出了$f(w_n^4)$的值；算出了$f(w_n^1)$，就算出來$f(w_n^5)$的值；...；算出了$f(w_n^3)$的值，就算出了$f(w_n^7)$的1值
?
同理，算$f_1(w_n^i)$和$f_2(w_n^i)$的值的時(shí)候，也是算出一半，得到另一半的值------每次解決問題，都會(huì)變成解決一半問題然后直接得到另一半的答案，在解決這一半問題的時(shí)候，也變成了解決一半的一半的問題，另一半的一半的問題又被解決。
?
這樣，就可以把$f(w_n^0),f(w_n^1),f(w_n^2),...,f(w_n^{n-1})$的值全部算出來，得到了n個(gè)點(diǎn)的值；同理算出$g(w_n^0),g(w_n^1),f(w_n^2),...,g(w_n^{n-1})$的值。得到了f(x)和g(x)的點(diǎn)值表示法，點(diǎn)值表示法相乘，O(n)復(fù)雜度就得到了f(x)*g(x)的點(diǎn)值表示法。
?
代碼如下：
#include <complex>//c++自帶復(fù)數(shù)模板 typedef complex<double> Complex;//重定義數(shù)據(jù)類型，記得要用double類型 void FFT(Complex *a,int n,int inv){ //a是你要進(jìn)行變換的數(shù)組（多項(xiàng)式系數(shù)數(shù)組），n是數(shù)組大小，inv暫時(shí)不管，你就當(dāng)做它等于1 if(n==1) return;//如果分治后的序列大小為1，就直接返回，不用繼續(xù)分治了 int mid=n>>1;//如果n不等于1，那就繼續(xù)分治，mid是分治后變成兩個(gè)序列的長(zhǎng)度 static Complex b[1000];//創(chuàng)建一個(gè)輔助用的b數(shù)組，后面體現(xiàn)用處 for(int i=0;i<mid;i++) b[i]=a[2*i],b[i+mid]=a[2*i+1];//將a數(shù)組奇數(shù)位置的值和偶數(shù)位置的值分開，b數(shù)組前mid個(gè)位置存a數(shù)組偶數(shù)位置值，后mid個(gè)位置存a數(shù)組奇數(shù)位置值 for(int i=0;i<n;i++) a[i]=b[i];//將b數(shù)組值重新賦給a數(shù)組 //對(duì)分治后的兩個(gè)序列（一個(gè)是a數(shù)組前mid個(gè)元素組成的序列，另一個(gè)數(shù)a數(shù)組后mid元素組成的序列） 進(jìn)行FFT變換 FFT(a,mid,inv); FFT(a+mid,mid,inv);//算出一半，得到另一半的值，a數(shù)組前mid元素相當(dāng)于之前說的f1，a數(shù)組后mid元素相當(dāng)于之前說的f2 for(int i=0;i<mid;i++){Complex com(cos(2*pi*i/n),inv*sin(2*pi*i/n));b[i]=a[i]+com*a[i+mid];b[i+mid]=a[i]-com*a[i+mid];}for(int i=0;i<n;i++) a[i]=b[i];//重新將b數(shù)組賦值給a數(shù)組 return; } FFT變換（遞歸版）?
這里再來詳細(xì)解釋一下，上面代碼中的n值
加入開始兩個(gè)序列是n次多項(xiàng)式和m次多項(xiàng)式，那么開始n值就等于大于等于$(m+n)$的最小2次冪，如下代碼所示
cin>>n>>m; int k=n+m,lim=1; while(k>>=1) lim<<=1; if(lim<n+m) lim<<=1; FFT(a,lim,1);//對(duì)a序列進(jìn)行變換 FFT(b,lim,1);//對(duì)b序列進(jìn)行變換此時(shí)lim值就是n的初值
?
強(qiáng)調(diào)一遍$$w_n^k=cos\frac{2k\pi}{n}+i\,sin\frac{2k\pi}{n}$$
?
?
?
FFT逆變換
?
FFT逆變換則是將點(diǎn)值表示法轉(zhuǎn)化為系數(shù)表示法的步驟。在逆變換之前，我們已經(jīng)對(duì)兩個(gè)多項(xiàng)式系數(shù)序列進(jìn)行了正變換，即
FFT(a,lim,1);//正變換 FFT(b,lim,1); for(int i=0;i<lim;i++) a[i]=a[i]*b[i];//將正變換的兩個(gè)序列乘在一起，得到新的多項(xiàng)式的點(diǎn)值表示法序列。?
?
如上所示，只要將a序列進(jìn)行逆變換，就可以得到新多項(xiàng)式的系數(shù)序列。在FFT正變換之中，我們一直在求$f(w_n^i)$的值。
假設(shè)所求多項(xiàng)式系數(shù)序列為$k_0,k_1,...k_{n-1}$
?
現(xiàn)在對(duì)于新的多項(xiàng)式a（新得到的序列，不是原來的a序列）來求卷積$$c_h=\sum_{i=0}^{n-1}a_i(w_n^{-h})^i$$
相當(dāng)于對(duì)a序列又進(jìn)行FFT變換，只不過，我們現(xiàn)在以新序列a為系數(shù)的多項(xiàng)式在$x=w_n^{-i}$的一系列值
相當(dāng)于求$C(x)=a_0+a_1x+a_2x^2+...+a_{n-1}x^{n-1}$在$x=w_n^0,w_n^-1,w_n^{-2},...w_n^{-(n-1)}$的點(diǎn)值表示法
而我們知道$a_x=k_0+k_1w_n^x+k_2(w_n^k)^2+...=\sum_{j=0}^{n-1}k_j(w_n^x)^j$
?
$$\sum_{i=0}^{n-1}a_i(w_n^{-h})^i$$
$$=\sum_{i=0}^{n-1}(\sum_{j=0}^{n-1}k_j*(w_n^i)^j)(w_n^{-h})^i$$
$$=\sum_{j=0}^{n-1}k_j(\sum_{i=0}^{n-1}(w_n^{j-h})^i)$$
$$=\sum_{j=0}^{n-1}k_j(\sum_{i=0}^{n-1}w_n^{(j-h)*i})$$
?
由于當(dāng)且只當(dāng)$j=h$時(shí)，$(j-h)$才為i的倍數(shù)，其余時(shí)候?yàn)?，根據(jù)n次單位根更加復(fù)雜的性質(zhì)可得（不知道的看看n次單位根預(yù)備性質(zhì)）
$$\sum_{j=0}^{n-1}k_j(\sum_{i=0}^{n-1}w_n^{(j-h)*i})$$
$$=n*k_h$$
所以
$$k_h=\frac {\sum_{i=0}^{n-1}a_i(w_n^{-h})^i}{h}=\frac {c_h}{n}$$
?
說明：$w_n^{-i}$與$w_n^i$實(shí)部相同，虛部相反。現(xiàn)在知道代碼中inv的作用了吧
當(dāng)inv=1，表示FFT變換；當(dāng)inv=-1，表示FFT逆變換
?
FFT(a,lim,1); FFT(b,lim,1); for(int i=0;i<lim;i++) a[i]=a[i]*b[i]; FFT(a,lim,-1); //經(jīng)過FFT逆變換之后，a序列虛部都已經(jīng)為0，只有實(shí)部有值，且為整數(shù) for(int i=0;i<n+m-1;i++) printf("%d ",(int)(a[i].real()/lim+0.5));//實(shí)部根據(jù)前面推導(dǎo)要除以n（這里除以lim）為啥要加0.5捏：首先我們確定答案肯定是整數(shù)，但是在代碼實(shí)現(xiàn)過程中，由于有$\pi$介入計(jì)算，導(dǎo)致答案可能變小了（誤差很小），所以加一個(gè)0.5，然后強(qiáng)制類型轉(zhuǎn)換切掉小數(shù)部位
比如說本來答案是1，但是代碼實(shí)現(xiàn)的結(jié)果可能是0.999999999999，此時(shí)加上了0.5，然后轉(zhuǎn)換為int，答案就是1了。
?
強(qiáng)調(diào)一遍$$w_n^k=cos\frac{2k\pi}{n}+i\,sin\frac{2k\pi}{n}$$
FFT代碼
#include <complex>//c++自帶復(fù)數(shù)模板 typedef complex<double> Complex;//重定義數(shù)據(jù)類型，記得要用double類型 void FFT(Complex *a,int n,int inv){ //a是你要進(jìn)行變換的數(shù)組（多項(xiàng)式系數(shù)數(shù)組），n是數(shù)組大小，inv=1表示正變換，inv=-1表示逆變換 if(n==1) return;//如果分治后的序列大小為1，就直接返回，不用繼續(xù)分治了 int mid=n>>1;//如果n不等于1，那就繼續(xù)分治，mid是分治后變成兩個(gè)序列的長(zhǎng)度 static Complex b[1000];//創(chuàng)建一個(gè)輔助用的b數(shù)組，后面體現(xiàn)用處 for(int i=0;i<mid;i++) b[i]=a[2*i],b[i+mid]=a[2*i+1];//將a數(shù)組奇數(shù)位置的值和偶數(shù)位置的值分開，b數(shù)組前mid個(gè)位置存a數(shù)組偶數(shù)位置值，后mid個(gè)位置存a數(shù)組奇數(shù)位置值 for(int i=0;i<n;i++) a[i]=b[i];//將b數(shù)組值重新賦給a數(shù)組 //對(duì)分治后的兩個(gè)序列（一個(gè)是a數(shù)組前mid個(gè)元素組成的序列，另一個(gè)數(shù)a數(shù)組后mid元素組成的序列） 進(jìn)行FFT變換 FFT(a,mid,inv); FFT(a+mid,mid,inv);//算出一半，得到另一半的值，a數(shù)組前mid元素相當(dāng)于之前說的f1，a數(shù)組后mid元素相當(dāng)于之前說的f2 for(int i=0;i<mid;i++){Complex com(cos(2*pi*i/n),inv*sin(2*pi*i/n));b[i]=a[i]+com*a[i+mid];b[i+mid]=a[i]-com*a[i+mid];}for(int i=0;i<n;i++) a[i]=b[i];//重新將b數(shù)組賦值給a數(shù)組 return; } FFT變換?
?
?
?
?
FFT系數(shù)儲(chǔ)存注意
?
在進(jìn)行FFT之前，我們有兩個(gè)多項(xiàng)式系數(shù)序列，用數(shù)組存系數(shù)的不要用普通的數(shù)組存，而要用復(fù)數(shù)數(shù)組，因?yàn)樵谟?jì)算的時(shí)候系數(shù)涉及復(fù)數(shù)計(jì)算，所以這樣
#include <complex>//c++自帶復(fù)數(shù)模板 Complex a[1000],b[1000];for(int i=0;i<n;i++) scanf("%d",&t),a[i]=Complex(t,0);//構(gòu)造函數(shù) for(int i=0;i<m;i++) scanf("%d",&t),b[i]=Complex(t,0);這樣，復(fù)數(shù)的實(shí)部存系數(shù)的值，虛部為0
?
一個(gè)算多項(xiàng)式相乘后系數(shù)序列的程序
//開頭說明一下，最下面有輸入輸出樣例 #include <iostream>#include <cmath> #define pi acos(-1)#include <complex>//c++自帶復(fù)數(shù)模板 using namespace std; typedef complex<double> Complex;//重定義數(shù)據(jù)類型，記得要用double類型 Complex a[1000],b[1000]; int n,m;void FFT(Complex *a,int n,int inv){ //a是你要進(jìn)行變換的數(shù)組（多項(xiàng)式系數(shù)數(shù)組），n是數(shù)組大小，inv=1表示正變換，inv=-1表示逆變換 if(n==1) return;//如果分治后的序列大小為1，就直接返回，不用繼續(xù)分治了 int mid=n>>1;//如果n不等于1，那就繼續(xù)分治，mid是分治后變成兩個(gè)序列的長(zhǎng)度 static Complex b[1000];//創(chuàng)建一個(gè)輔助用的b數(shù)組，后面體現(xiàn)用處 for(int i=0;i<mid;i++) b[i]=a[2*i],b[i+mid]=a[2*i+1];//將a數(shù)組奇數(shù)位置的值和偶數(shù)位置的值分開，b數(shù)組前mid個(gè)位置存a數(shù)組偶數(shù)位置值，后mid個(gè)位置存a數(shù)組奇數(shù)位置值 for(int i=0;i<n;i++) a[i]=b[i];//將b數(shù)組值重新賦給a數(shù)組 //對(duì)分治后的兩個(gè)序列（一個(gè)是a數(shù)組前mid個(gè)元素組成的序列，另一個(gè)數(shù)a數(shù)組后mid元素組成的序列） 進(jìn)行FFT變換 FFT(a,mid,inv); FFT(a+mid,mid,inv);//算出一半，得到另一半的值，a數(shù)組前mid元素相當(dāng)于之前說的f1，a數(shù)組后mid元素相當(dāng)于之前說的f2 for(int i=0;i<mid;i++){Complex com(cos(2*pi*i/n),inv*sin(2*pi*i/n));b[i]=a[i]+com*a[i+mid];b[i+mid]=a[i]-com*a[i+mid];}for(int i=0;i<n;i++) a[i]=b[i];//重新將b數(shù)組賦值給a數(shù)組 return; } int main(){cin>>n>>m;//輸入兩個(gè)多項(xiàng)式的項(xiàng)數(shù) int k=n+m,lim=1,t;for(int i=0;i<n;i++) scanf("%d",&t),a[i]=Complex(t,0);//第一個(gè)多項(xiàng)式系數(shù) for(int i=0;i<m;i++) scanf("%d",&t),b[i]=Complex(t,0);//第二個(gè)多項(xiàng)式系數(shù) while(k>>=1) lim<<=1;if(lim<n+m) lim<<=1;FFT(a,lim,1);FFT(b,lim,1);for(int i=0;i<lim;i++) a[i]=a[i]*b[i];FFT(a,lim,-1);for(int i=0;i<n+m-1;i++) printf("%d ",(int)(a[i].real()/lim+0.5)); } /* //輸入 2 3//第一個(gè)多項(xiàng)式有兩項(xiàng) ，第二個(gè)多項(xiàng)式有三項(xiàng) 1 2//第一個(gè)多項(xiàng)式為(1+2x) 2 1 2//第二個(gè)多項(xiàng)式為(2+x+2x^2) //輸出 2 5 4 4//(1+2x)*(2+x+2x^2)=2+5x+4x^2+4x^3,系數(shù)為2 5 4 4*/ 多項(xiàng)式相乘測(cè)試用例
//輸入 2 2//兩個(gè)多項(xiàng)式都有兩項(xiàng) 1 1//第一個(gè)多項(xiàng)式為(1+x) 1 1//第二個(gè)多項(xiàng)式為(1+x) //輸出 1 2 1//(1+x)*(1+x)=1+2*x+x^2,系數(shù)為1 2 1 測(cè)試?
?
?
?
FFT變換的示例演示
?
在講FFT迭代版本之前，我打算先用一個(gè)例子來展示FFT變換，加深認(rèn)識(shí)
假設(shè)
多項(xiàng)式$f(x)=3+2x+x^2$
多項(xiàng)式$g(x)=2+x+2x^2$
在草稿紙上算一下，這兩個(gè)多項(xiàng)式相乘的結(jié)果為$h(x)=6+7x+10x^2+5x^3+2x^4$
?
先得到$f(x)$與$g(x)$多項(xiàng)式的系數(shù)序列，注意應(yīng)該寫成復(fù)數(shù)形式的序列（復(fù)數(shù)形式為(real,image)）
多項(xiàng)式$f(x)$的系數(shù)序列為$A=\left\{(3,0),(2,0),(1,0)\right\}$
多項(xiàng)式$g(x)$的系數(shù)序列為$B=\left\{(2,0),(1,0),(2,0)\right\}$
?
然后判斷兩個(gè)多項(xiàng)式相乘后有多少項(xiàng)，應(yīng)該不超過3+3=6項(xiàng)。而大于6的最小2次冪應(yīng)該為8，所以要把兩個(gè)多項(xiàng)式序列補(bǔ)成8項(xiàng)。
?
故（用(0,0)來補(bǔ)項(xiàng)）
多項(xiàng)式$f(x)$的系數(shù)序列為$A=\left\{(3,0),(2,0),(1,0),(0,0),(0,0),(0,0),(0,0),(0,0)\right\}$
多項(xiàng)式$g(x)$的系數(shù)序列為$B=\left\{(2,0),(1,0),(2,0),(0,0),(0,0),(0,0),(0,0),(0,0)\right\}$
?
然后將每一個(gè)序列分成長(zhǎng)度為2的小序列
?
后面的是重點(diǎn)，對(duì)于每一個(gè)長(zhǎng)度為2的小序列（設(shè)為(x,y)）:
第一個(gè)元素$x$重新賦值為$x+w_1^0*y$
第二個(gè)元素$y$重新賦值為$x-w_1^0*y$
(這個(gè)$w_1^1$這樣來的：$w_{當(dāng)前序列一半長(zhǎng)度l}^{一半長(zhǎng)度l的第i個(gè)元素,i從0到l-1}$)
重新賦值完之后就可以合并了，每?jī)蓚€(gè)長(zhǎng)度為2的相鄰序列合并為一個(gè)長(zhǎng)度為4的序列
?
對(duì)于每一個(gè)長(zhǎng)度為4的序列（設(shè)為(a,b,c,d)）:
第一個(gè)元素$a$重新賦值為$a+w_2^0*c$
第三個(gè)元素$c$重新賦值為$a-w_2^0*c$
第二個(gè)元素$b$重新賦值為$b+w_2^1*d$
第四個(gè)元素$d$重新賦值為$b-w_2^1*d$
重新賦值完之后就可以合并了，每?jī)蓚€(gè)長(zhǎng)度為4的相鄰序列合并為一個(gè)長(zhǎng)度為8的序列（此時(shí)全部小序列已經(jīng)合并為一個(gè)序列了）
?
對(duì)于整個(gè)序列（長(zhǎng)度為8），按照上面的賦值方法重新賦值（可以參考代碼），于是FFT變換就ok了
兩個(gè)序列就變成了
$A=\left\{A_0',A_1',A_2',A_3',A_4',A_5',A_6',A_7'\right\}$
$B=\left\{B_0',B_1',B_2',B_3',B_4',B_5',B_6',B_7'\right\}$
將兩個(gè)序列對(duì)應(yīng)元素相乘，得到新序列
$C=\left\{A_0'*B_0',A_1'*B_1',A_2'*B_2',A_3'*B_3',A_4'*B_4',A_5'*B_5',A_6'*B_6',A_7'*B_7'\right\}$
然后將C序列進(jìn)行FFT逆變換，就是多項(xiàng)式相乘后的系數(shù)序列了。
?
ps：FFT逆變換就是把當(dāng)前序列再來一次FFT變換，只不過在重新賦值環(huán)節(jié)的時(shí)候是乘上$w_{mid}^{-1}$，而不是$w_{mid}^i$，最后得到的序列虛部為0，將實(shí)部全部除以8即可（這里不懂參考代碼或前面逆變換的講解）
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
轉(zhuǎn)載于:https://www.cnblogs.com/qiyueliu/p/11237318.html
總結(jié)
以上是生活随笔為你收集整理的学习：多项式算法----FFT的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： linux查看openssh和opens
- 下一篇： 3Delight粒子渲染，真快。