【模板】快速傅里叶变换

还是一份常数很大的板子，我再卡一卡罢。

#include <iostream>
#include <complex>
#include <cmath>
const int N = 1100010;
const double pi = 3.14159265358979323846;
std :: complex<double> a[N];
int n, m, max_bit, max_val;
int rev[N];
double sin_save[N], cos_save[N];
void fft_init() {
	for(int i = 0;i < max_val;++i) 
		rev[i] = (rev[i>>1]>>1)|((i&1)<<(max_bit-1));
	for(int i = 1;i < max_val;i <<= 1) {
		sin_save[i] = sin(pi/i);
		cos_save[i] = cos(pi/i);
	}
}
void FFT(std :: complex<double> *f,const int opt) {
	for(int i = 0;i < max_val;++i) 
		if(i < rev[i]) 
			std :: swap(f[i],f[rev[i]]);
	for(int p_1 = 1, p_2 = 2;p_1 < max_val;p_1 <<= 1, p_2 <<= 1) {
		std :: complex<double> w_n(cos_save[p_1],opt*sin_save[p_1]);
		for(int j = 0;j < max_val;j += p_2) {
			std :: complex<double> w(1,0);
			for(int k = j;k < j+p_1;++k, w *= w_n) {
				std :: complex<double> x(w*f[k+p_1]);
				f[k+p_1] = f[k]-x;
				f[k] += x;
			}
		}
	}
}
char ch_in;
short get_single() {
	ch_in = getchar();
	while(ch_in < '0') 
		ch_in = getchar();
	return ch_in&15;
}
int main() {
	scanf("%d %d",&n,&m);
	for(int i = 0;i <= n;++i) 
		a[i].real(get_single());
	for(int i = 0;i <= m;++i) 
		a[i].imag(get_single());
	max_val = 1<<(max_bit = 31-__builtin_clz(n+m));
	if((n+m)&max_val) {
		max_val <<= 1;
		++max_bit;
	}
	fft_init();
	FFT(a,1);
	for(int i = 0;i < max_val;++i) 
		a[i] *= a[i];
	FFT(a,-1);
	for(int i = 0;i <= n+m;++i) 
		printf("%d ",(int)(a[i].imag()/(max_val<<1)+0.5));
	return 0;
}

原文地址：http://www.cnblogs.com/bikuhiku/p/Fast_Fourier_Transform.html