带预处理的，听说精度会炸=w=
void DFT(complex *a,int flag) { for(int i=0;i<len;i++) { int p=0; for(int j=i,k=0;k<lg;j/=2,k++) p=(p<<1)+(j&1); t[p]=a[i]; } for(int m=2;m<=len;m=(m<<1)) { int half=m/2,times = len/m; for(int i=0;i<half;i++) { complex w= (flag>0)? W[i*times] : W[len-i*times]; for(int j=i;j<len;j+=m) { complex u=t[j],v=t[j+half]*w; t[j]=u+v; t[j+half]=u-v; } } } for(int i=0;i<len;i++) a[i]=t[i]; if (flag==-1) for(int i=0;i<len;i++) a[i].real/=len; } void FFT(db *A,db *B,db *C) { for(int i=0;i<len;i++) { a[i].real=A[i]; b[i].real=B[i]; } W[0].real=1;W[1]=complex(cos(2*pi/len),sin(2*pi/len)); for(int i=2;i<=len;i++) W[i]=W[i-1]*W[1]; DFT(a,1);DFT(b,1); for(int i=0;i<len;i++) c[i]=a[i]*b[i]; DFT(c,-1); for(int i=0;i<len;i++) C[i]=c[i].real; }