【模板】多项式乘法 FFT

posted on 2022-08-02 23:57:12 | under 模板 | source

涉世不深，不会卡常，恳求大佬指教

typedef complex<double> comp;
const double PI=acos(-1);
template<int N> struct rever{
	int rev[1<<N];
	rever(){for(int i=rev[0]=0;i<1<<N;i++) rev[i]=rev[i>>1]>>1|(i&1)<<(N-1);}
	template<class T> void make(T a[]){for(int i=0;i<1<<N;i++) if(i<rev[i]) swap(a[i],a[rev[i]]);}
};
rever<18> rev;
template<int N> struct poly{
	comp a[N];
	comp& operator[](int i){return a[i];}
	poly& operator*=(poly &b){for(int i=0;i<N;i++) a[i]*=b[i];return *this;}
	void fft(int flag){
		rev.make(a);
		for(int mid=1;mid<N;mid<<=1){
			comp wn(cos(PI/mid),flag*sin(PI/mid));
			for(int j=0;j<N;j+=mid<<1){
				comp w(1,0);
				for(int k=0;k<mid;k++,w=w*wn){
					comp x=a[j+k],y=w*a[j+mid+k];
					a[j+k]=x+y,a[j+mid+k]=x-y;
				}
			}
		}
		if(flag==-1) for(int i=0;i<N;i++) a[i]/=N;
	}
};