还是一份常数很大的板子,我再卡一卡罢。
#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;
}
标签:ch,val,变换,max,rev,int,save,傅里叶,模板
From: https://www.cnblogs.com/bikuhiku/p/Fast_Fourier_Transform.html