FFT模板
ｃｏｄｅ：
#include <bits/stdc++.h> using namespace std; typedef long long ll; bool Finish_read; template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;} template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x+'0');} template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');} template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);} /*================Header Template==============*/ const int maxn=5e6+500; const double PI=acos(-1); int n,m; int rev[maxn]; int lim=1,len; /*==================Define Area================*/ struct comp { double r,i; comp() {} comp(double r,double i):r(r),i(i) {} }a[maxn],b[maxn]; comp operator + (comp a,comp b) { return comp(a.r+b.r,a.i+b.i); } comp operator - (comp a,comp b) { return comp(a.r-b.r,a.i-b.i); } comp operator * (comp a,comp b) { return comp(a.r*b.r-a.i*b.i,a.i*b.r+a.r*b.i); } void GetRev() { for(int i=0;i<lim;i++) { rev[i]=(rev[i>>1]>>1)|((i&1)<<(len-1)); } } void FFT(comp *a,int IDFT) { for(int i=0;i<lim;i++) if(i<rev[i]) swap(a[i],a[rev[i]]); for(int mid=1;mid<lim;mid<<=1) { comp w=comp(cos(PI/mid),IDFT*sin(PI/mid)); for(int l=mid<<1,j=0;j<lim;j+=l) { comp wn=comp(1.0,0.0); for(int k=0;k<mid;k++) { comp x=a[k+j]; comp y=a[k+j+mid]*wn; a[k+j]=x+y; a[k+j+mid]=x-y; wn=wn*w; } } } } int main() { read(n);read(m); while(lim<=n+m) lim<<=1,len++; GetRev(); for(int i=0;i<=n;i++) scanf("%lf",&a[i].r); for(int i=0;i<=m;i++) scanf("%lf",&b[i].r); FFT(a,1); FFT(b,1); for(int i=0;i<lim;i++) { a[i]=a[i]*b[i]; } FFT(a,-1); for(int i=0;i<=m+n;i++) { printf("%d ",(int)(a[i].r/lim+0.5)); } return 0; }转载于:https://www.cnblogs.com/Apocrypha/p/9430637.html
相关资源：JAVA上百实例源码以及开源项目