计蒜客♂计蒜客♂计蒜客♂计蒜客

[模板]FFT

2019-04-01 19:40:19


#include <bits/stdc++.h>
using namespace std;
const int maxn = 10000010;
const double PI = acos(-1.0);
struct Complex{
    double xx,yy;
    Complex(){}
    Complex(double _xx,double _yy){
        xx = _xx;
        yy = _yy;
    }
};
Complex operator + (const Complex &a,const Complex &b){
    return Complex(a.xx+b.xx,a.yy+b.yy);
}
Complex operator - (const Complex &a,const Complex &b){
    return Complex(a.xx-b.xx,a.yy-b.yy);
}
Complex operator * (const Complex &a,const Complex &b){
    return Complex(a.xx*b.xx-a.yy*b.yy,a.xx*b.yy+a.yy*b.xx);
}
int lim = 1;
int l=0,r[maxn];
Complex a[maxn],b[maxn];
void FFT(Complex *A,int type){
    for(int i=0;i<lim;i++){
        if(i < r[i]) swap(A[i],A[r[i]]);
    }
    for(int mid = 1;mid<lim;mid<<=1){
        Complex Wn(cos(PI/mid),type*sin(PI/mid));
        //单位根
        for(int R=mid<<1,j=0;j<lim;j+=R){
            Complex w(1,0);
            for(int k=0;k<mid;k++,w=w * Wn)
            {
                Complex x = A[j+k];
                Complex y = w * A[j+mid+k];
                A[j + k] = x + y;
                A[j + mid + k] = x - y;
            }
        } 
    }
}
int n,m;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<=n;i++) {
        int tmp;
        scanf("%d",&tmp);
        a[i].xx = tmp;
    }
    for(int i=0;i<=m;i++) {
        int tmp;
        scanf("%d",&tmp);
        b[i].xx = tmp;
    }
    while(lim <= n+m){
        lim <<= 1;
        l++;
    }
    for(int i=0;i<lim;i++){
        r[i] = (r[i>>1] >> 1) | ((i & 1) << (l-1));
        //printf("r[%d]=%d\n",i,r[i]);
    }
    //printf("l:%d lim:%d\n",l,lim);
    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<=n+m;i++){
        printf("%d ",(int)(a[i].xx / lim + 0.5));
    }
    return 0;
}