FFT模版题
话说网上对FFT讲的神乎其神，以后我来搞一份小学生都能看懂的FFT入门吧
最好没有公式和严谨的证明，搞一些非常通俗的就比较好
因为我自己也只会模版。。。
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const int SIZE=300005;
const double Pi=acos(-1);
int An,Bn,Cn,n,Step,Rev[SIZE],Ans[SIZE];
char s[SIZE];
struct Complex{
double a,b;
Complex(double sa=0.0,double sb=0.0){a=sa;b=sb;}
friend Complex operator+(Complex a,Complex b){return Complex(a.a+b.a,a.b+b.b);}
friend Complex operator-(Complex a,Complex b){return Complex(a.a-b.a,a.b-b.b);}
friend Complex operator*(Complex a,Complex b){return Complex(a.a*b.a-a.b*b.b,b.a*a.b+a.a*b.b);}
}A[SIZE],B[SIZE],C[SIZE];
void FFT(Complex *x,int flag){
for(int i=0;i<n;i++)if(i<Rev[i])swap(x[i],x[Rev[i]]);
for(int k=1;k<n;k<<=1){
Complex wk=Complex(cos(Pi/k),flag*sin(Pi/k));
for(int i=0;i<n;i+=k<<1){
Complex wkj=Complex(1.0,0.0);
for(int j=0;j<k;j++){
Complex a=x[i+j],b=x[i+j+k]*wkj;
x[i+j]=a+b;
x[i+j+k]=a-b;
wkj=wkj*wk;
}
}
}
if(flag==-1)for(int i=0;i<n;i++)x[i].a/=n;
}
void Init_Solve_Out(){
scanf("%d",&An);
Bn=An;Cn=An+Bn-1;
scanf("%s",s);
for(int i=0;i<An;i++)A[i]=Complex(s[i]-'0');
scanf("%s",s);
for(int i=0;i<Bn;i++)B[i]=Complex(s[i]-'0');
for(n=1,Step=0;n<Cn;n<<=1,Step++);
for(int i=0;i<n;i++)Rev[i]=(Rev[i>>1]>>1)|((i&1)<<(Step-1));
FFT(A,1);FFT(B,1);
for(int i=0;i<n;i++)C[i]=A[i]*B[i];
FFT(C,-1);
for(int i=0;i<Cn;i++)Ans[Cn-i]=(int)(C[i].a+0.5);
for(int i=1;i<=Cn;i++)Ans[i+1]+=Ans[i]/10,Ans[i]%=10;
if(Ans[Cn+1])Cn++;
for(int i=Cn;i>=1;i--)printf("%d",Ans[i]);
}
int main(){
freopen("2179.in","r",stdin);
freopen("2179.out","w",stdout);
Init_Solve_Out();
return 0;
}
评论 (0)
