Artifact 30aac07db1a49b69289dcfa47ac8a123493d0214
//-------------------------------------------------------------
// Fast Discrete Fourier Transform
// O(n log n)
// n must be a power of 2.
//
// Verified by
// - SRM 436 LV3
//-------------------------------------------------------------
CMP tmp[65536*4];
template<int F>
void fft_impl( CMP a[], int n, int stride = 1 )
{
if( n > 1 )
{
CMP *ev=a, *od=a+stride;
int s2=stride*2, n2=n/2;
fft_impl<F>( ev, n2, s2 );
fft_impl<F>( od, n2, s2 );
for(int i=0; i<n; ++i) tmp[i] = ev[s2*(i%n2)] + od[s2*(i%n2)]*polar(1.0, F*2*M_PI*i/n);
for(int i=0; i<n; ++i) a[stride*i] = tmp[i];
}
}
void fft( vector<CMP>& a )
{
fft_impl<+1>(&a[0], a.size());
}
void ifft( vector<CMP>& a )
{
fft_impl<-1>(&a[0], a.size());
for(int i=0; i<a.size(); ++i)
a[i] /= a.size();
}