FFT基础模板

本文主要是介绍FFT基础模板，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 传送门

#include<bits/stdc++.h>
#define il inline
#define pb push_back
#define ms(_data,v) memset(_data,v,sizeof(_data))
#define sc(n) scanf("%d",&n)
#define SC(n,m) scanf("%d %d",&n,&m)
#define SZ(a) int((a).size())
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define drep(i,a,b)	for(int i=a;i>=b;--i)
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const double pi=acos(-1.0);
const double eps=1e-9;//il int add(int x,int y) {return x+y>=mod?x+y-mod:x+y;}
//il int mul(ll x,int y) {return x*y>=mod?x*y%mod:x*y;}
const int N=5e6+5;
int n,m;
int limit=1,L=0,r[N];
struct Complex {double x,y;Complex(double xx=0,double yy=0) {x=xx,y=yy;}Complex operator + (const Complex &b) const {return Complex(x+b.x,y+b.y);}Complex operator - (const Complex &b) const {return Complex(x-b.x,y-b.y);}Complex operator * (const Complex &b) const {return Complex(x*b.x-y*b.y,x*b.y+y*b.x);}
} a[N],b[N];
il void FFT(Complex *A,int opt) {for(int i=0; i<limit; i++) {if(i<r[i]) swap(A[i],A[r[i]]);}for(int mid=1; mid<limit; mid<<=1) {Complex Wn(cos(pi/mid),opt*sin(pi/mid));for(int R=mid<<1,j=0; j<limit; j+=R) {Complex W(1,0);for(int k=0; k<mid; k++,W=W*Wn) {Complex x=A[j+k],y=W*A[j+mid+k];A[j+k]=x+y;A[j+mid+k]=x-y;}}}
}
il void Solve(Complex *a,Complex *b) {while(limit<=n+m) limit<<=1,L++;for(int i=0; i<limit; i++) r[i]=(r[i>>1]>>1)|((i&1)<<(L-1)); // 预处理FFT(a,1),FFT(b,1);for(int i=0; i<=limit; i++) a[i]=a[i]*b[i];FFT(a,-1);
}
int main() {scanf("%d%d",&n,&m);for(int i=0; i<=n; i++) scanf("%lf",&a[i].x); // n次多项式for(int i=0; i<=m; i++) scanf("%lf",&b[i].x); // m次多项式Solve(a,b);//求出两多项式卷积for(int i=0; i<=n+m; i++)printf("%d ",(int)(a[i].x/limit+0.5)); //输出指数为i的系数return 0;
}

 

这篇关于FFT基础模板的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---