快速傅里叶变换模板题
算法理解请看《算法导论》第30章《多项式与快速傅里叶变换》，至于证明插值唯一性什么的看不懂也没关系啦～只要明白这个过程是怎么算的就ok。
递归版：(4252ms 23468kb)
//UOJ 34 递归版
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<complex>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
using namespace std;
const int N=;
void read(int &v){
v=;int sign=; char ch=getchar();
while(ch<'' || ch>'') {if (ch=='-') sign=-; ch=getchar();}
while(ch>=''&&ch<=''){v=v*+ch-''; ch=getchar();}
v*=sign;
}
/****************tamplate***********************/
const double PI=acos(-);
typedef complex<double> comp;
comp a[N],b[N],c[N];
void FFT(comp a[],int n,int type){
if (n==) return;
int i;
comp y0[n>>],y1[n>>];
for(int i=;i<n;i+=)
y0[i>>]=a[i],y1[i>>]=a[i+];
FFT(y0,n>>,type); FFT(y1,n>>,type);
comp w0( cos(type**PI/n) , sin(type**PI/n) ), w(,);
for(i=;i<(n>>);i++,w*=w0)
a[i]=y0[i]+w*y1[i],a[i+(n>>)]=y0[i]-w*y1[i];
}
int main(){
int i,temp,n,m;
read(n); read(m);
int x;
F(i,,n) read(x),a[i].real()=x;
F(i,,m) read(x),b[i].real()=x;
for(temp=;temp<=m+n;temp<<=);
FFT(a,temp,); FFT(b,temp,);
rep(i,temp) c[i]=a[i]*b[i];
FFT(c,temp,-);
for(int i=;i<=m+n;++i)
printf("%d ",int(c[i].real()/temp+0.5));
puts("");
return ;
}
迭代版：（1228ms 48088kb）（空间浪费了，其实用不了这么大）
//UOJ 34 迭代版
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<complex>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
using namespace std;
const int N=;
void read(int &v){
v=;int sign=; char ch=getchar();
while(ch<'' || ch>'') {if (ch=='-') sign=-; ch=getchar();}
while(ch>=''&&ch<=''){v=v*+ch-''; ch=getchar();}
v*=sign;
}
/****************tamplate***********************/
const double pi=acos(-);
typedef complex<double> comp;
comp a[N],b[N],c[N];
int n,m;
void FFT(comp *a,int n,int type){
for(int i=,j=;i<n-;i++){//j初始为i-1的位逆序置换？……每次算出i的位逆序置换j，下一次从j开始找（二进制加法）
//只改变1～n-2，0和n-1位置不变
for(int s=n;j^=s>>=,~j&s;);//
if (i<j) swap(a[i],a[j]);
}
for(int m=;m<n;m<<=){
double u=pi/m*type; comp wm(cos(u),sin(u));
for(int k=;k<n;k+=(m<<) ){
comp w(,);
for(int j=;j<m;j++){
comp &A=a[k+j+m],&B=a[k+j],t=w*A;
A=B-t; B=B+t; w=w*wm;
}
}
}
if (type==-) rep(i,n) a[i].real()/=n;
} int main(){
#ifndef ONLINE_JUDGE
freopen("FFT.in","r",stdin);
#endif
read(n); read(m);
int k=;
for(k=;k<=n||k<=m;k<<=); k<<=;
int x;
F(i,,n) read(x),a[i].real()=x;
F(i,,m) read(x),b[i].real()=x;
FFT(a,k,); FFT(b,k,);
rep(i,k) c[i]=a[i]*b[i];
FFT(c,k,-);
F(i,,n+m) printf("%d ",int(c[i].real()+0.5));
return ;
}
位逆序置换：（orz trz爷）(27~30行)
TRZ：比如我们要把一个二进制数加一，不是从最低位开始找到一个0，把它变成1，它之后的都变0嘛？那么现在我们有了i的位逆序表示，要求i+1的，不就是从最高位找0嘛，那个循环就是干这个事的。