[BZOJ2194]快速傅立叶之二（FFT）

题目描述

传送门

题解

度娘 卷积是两个变量在某范围内相乘后求和的结果。如果卷积的变量是序列x(n)和h(n)，则卷积的结果 y(n)=∑i=−∞+∞x(i)h(n−i)=x(n)∗h(n) 卷积定理指出，函数卷积的傅里叶变换是函数傅里叶变换的乘积。即，一个域中的卷积相当于另一个域中的乘积，例如时域中的卷积就对应于频域中的乘积。 F(g(x)∗f(x))=F(g(x))F(f(x))

这道题给出的不是一个卷积的形式，但是可以考虑将b倒置，然后原式就变成了 c(k)=∑a(i)b(n−i+k) 令 c(n+k)=c(k) ， c(n+k)=∑a(i)b(n−i+k) ，这就是一个卷积的形式了 最终要求 c(0..n−1) 实际上就是求 c(n..2n−1)

代码

#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; #define N 300005 const double pi=acos(-1.0); int tot,n,m,L,R[N]; struct complex { double x,y; complex(double X=0,double Y=0) { x=X,y=Y; } }a[N],b[N]; complex operator + (complex a,complex b) {return complex(a.x+b.x,a.y+b.y);} complex operator - (complex a,complex b) {return complex(a.x-b.x,a.y-b.y);} complex operator * (complex a,complex b) {return complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);} void FFT(complex a[N],int opt) { for (int i=0;i<n;++i) if (i<R[i]) swap(a[i],a[R[i]]); for (int k=1;k<n;k<<=1) { complex wn=complex(cos(pi/k),opt*sin(pi/k)); for (int i=0;i<n;i+=(k<<1)) { complex w=complex(1,0); for (int j=0;j<k;++j,w=w*wn) { complex x=a[i+j],y=w*a[i+j+k]; a[i+j]=x+y,a[i+j+k]=x-y; } } } } int main() { scanf("%d",&tot);n=tot-1; for (int i=0;i<=n;++i) scanf("%lf%lf",&a[i].x,&b[n-i].x); m=n+n; for (n=1;n<=m;n<<=1) ++L; for (int i=0;i<n;++i) R[i]=(R[i>>1]>>1)|((i&1)<<(L-1)); FFT(a,1);FFT(b,1); for (int i=0;i<=n;++i) a[i]=a[i]*b[i]; FFT(a,-1); for (int i=m-tot+1;i<=m;++i) printf("%d\n",(int)(a[i].x/n+0.5)); }