FFT 模板（手写 Complex 类，非递归实现）

【模板】fft.cpp

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i=l; i<r; i++)
using namespace std;
const double PI(acos(-1));

struct Complex{
    double r, i;
    Complex(double r, double i):r(r), i(i){}
    Complex(int n):r(cos(2*PI/n)), i(sin(2*PI/n)){}    //!!error-prone
    Complex():r(0), i(0){}    //default constructor
    Complex &operator *=(const Complex &a){
        double R=r*a.r-i*a.i, I=r*a.i+a.r*i;
        r=R, i=I;
        return *this;
    }
    Complex operator+(const Complex a){
        return Complex(r+a.r, i+a.i);
    }
    Complex operator-(const Complex a){
        return Complex(r-a.r, i-a.i);
    }
    Complex operator*(const Complex a){
        return Complex(r*a.r-i*a.i, r*a.i+a.r*i);
    }
    void out(){
        cout<<r<<' '<<i<<endl;
    }
};

const int N(1<<17);
int ans[N];
Complex a[N], b[N];
char s[N], t[N];

void bit_revrese_swap(Complex *a, int n){
    for(int i=1, j=n>>1, k; i<n-1; i++){
        if(i < j) swap(a[i],a[j]);
        //tricky
        for(k=n>>1; j>=k; j-=k, k>>=1);    //inspect the highest "1"
        j+=k;
    }
}

void FFT(Complex* a, int n, int t){
    bit_revrese_swap(a, n);
    for(int i=2; i<=n; i<<=1){
        Complex wi(i*t);
        for(int j=0; j<n; j+=i){
            Complex w(1, 0);
            for(int k=j, h=i>>1; k<j+h; k++){
                Complex t=w*a[k+h], u=a[k];
                a[k]=u+t;
                a[k+h]=u-t;
                w*=wi;
            }
        }
    }
    if(t==-1) rep(i, 0, n) a[i].r/=n;    //!!error-prone
}

int trans(int x){
    int i=0;
    for(; x>1<<i; i++);
    return 1<<i;
}

int main(){
    for(; ~scanf("%s%s", s, t); ){
        int n=strlen(s), m=strlen(t), l=trans(n+m-1);
        rep(i, 0, n) a[i]=Complex(s[n-1-i]-'0', 0);
        rep(i, n, l) a[i]=Complex(0, 0);
        rep(i, 0, m) b[i]=Complex(t[m-1-i]-'0', 0);
        rep(i, m, l) b[i]=Complex(0, 0);

        FFT(a, l, 1), FFT(b, l, 1);
        rep(i, 0, l) a[i]*=b[i];
        FFT(a, l, -1);
        rep(i, 0, l) ans[i]=(int)(a[i].r+0.5); ans[l]=0;    //error-prone
        rep(i, 0, l) ans[i+1]+=ans[i]/10, ans[i]%=10;
        int Complex=l;
        for(;Complex && !ans[Complex]; --Complex);
        for(; ~Complex; putchar(ans[Complex--]+'0'));    //error-prone
        puts("");
    }
    return 0;
}