NaiveMartin's Blog

namespace fft{
    typedef complex<double>cpx;
    double pi=acos(-1.0);cpx im(0,1);
    void run(cpx*a,int n,int s){
        for(int i=0;i<n;++i){
            int j=0;for(int k=0;(1<<k)<n;++k)j<<=1,j+=((i>>k)&1);
            if(i<j)swap(a[i],a[j]);
        }
        for(int i=1;(1<<i)<=n;++i){
            int m=(1<<i);cpx wm=exp(double(s)*im*2.0*pi/double(m));
            for(int j=0;j<n;j+=m){
                cpx w=1;
                for(int k=0;k<m/2;++k){
                    cpx u=a[j+k],v=w*a[j+k+m/2];
                    a[j+k]=u+v;a[j+k+m/2]=u-v;w*=wm;
                }
            }
        }
    }
}