猫史档案馆

转自本人洛谷博客 （洛谷id：wxy_

递归实现 FFT:

#include <iostream>
#include <cstdio>
#include <cmath>
#include <complex>
namespace wxy{
    const int N = 4.2e6;
    typedef std::complex<double> comp;
    comp a[N],b[N],c[N],tmp[N];int n,m;
    void DFT(comp *f,int len,int rev){
        if (len == 1) return;
        for (int i = 0; i < len; i++) tmp[i] = f[i];
        for (int i = 0; i < len; i++){
            if (i & 1) f[len + i >> 1] = tmp[i];
            else f[i >> 1] = tmp[i];
        }
        comp *g = f,*h = f + len / 2;
        DFT(g,len >> 1,rev);DFT(h,len >> 1,rev);
        comp cur(1,0),step(cos(2 * M_PI / len),sin(rev * 2 * M_PI / len));
        for (int i = 0; i < len >> 1; i++){
            tmp[i] = g[i] + cur * h[i];
            tmp[len / 2 + i] = g[i] - cur * h[i];
            cur *= step;
        }
        for (int i = 0; i < len; i++) f[i] = tmp[i];
    }
    void main(){
        std::cin >> n >> m;
        for (int i = 0; i <= n; i++) std::cin >> a[i];
        for (int i = 0; i <= m; i++) std::cin >> b[i];
        int limit = 1;while (limit <= n + m + 1) limit <<= 1;
        DFT(a,limit,1);DFT(b,limit,1);
        for (int i = 0; i < limit; i++) c[i] = a[i] * b[i];
        DFT(c,limit,-1);
        for (int i = 0; i <= n + m; i++) printf("%.0f ",fabs(c[i].real()/limit));
    }
}signed main(){wxy::main();return 0;}