bzoj2194: 快速傅立叶之二

时间：2023-03-08 16:17:21
 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 using namespace std;

 const int maxn=;

 const double PI=acos(-);

 struct node{

     double real,imag;

     void clear(){real=imag=;}

     node operator +(const node &x){return (node){real+x.real,imag+x.imag};}

     node operator -(const node &x){return (node){real-x.real,imag-x.imag};}

     node operator *(const node &x){return (node){real*x.real-imag*x.imag,real*x.imag+imag*x.real};}

 }a[maxn],b[maxn],c[maxn],t1,t2,w,wn;

 int m,n,len,rev[maxn],ans[maxn];

 void read(int &x){

     x=; int f=; char ch;

     for (ch=getchar();!isdigit(ch);ch=getchar()) if (ch=='-') f=-;

     for (;isdigit(ch);ch=getchar()) x=x*+ch-''; x*=f;

 }

 int Rev(int x){

     int temp=;

     for (int i=;i<=len;i++) temp<<=,temp+=(x&),x>>=;

     return temp;

 }

 void FFT(node *a,int op){

     for (int i=;i<n;i++) if (i<rev[i]) swap(a[i],a[rev[i]]);

     for (int s=;s<=n;s<<=){

         wn=(node){cos(*op*PI/s),sin(*op*PI/s)};

         for (int i=;i<n;i+=s){

             w=(node){,};

             for (int j=i;j<i+s/;j++,w=w*wn){

                 t1=a[j],t2=w*a[j+s/];

                 a[j]=t1+t2,a[j+s/]=t1-t2;

             }

         }

     }

 }

 int main(){

     read(m); n=,len=;

     while (n<(m<<)) n<<=,len++;

     for (int i=;i<n;i++) rev[i]=Rev(i);

     for (int x,i=;i<m;i++) read(x),a[i].real=x,read(x),b[m--i].real=x;

     FFT(a,),FFT(b,);

     for (int i=;i<n;i++) c[i]=a[i]*b[i];

     FFT(c,-);

     for (int i=;i<n;i++) ans[i]=(int)round(c[i].real/n);

     for (int i=m-;i<*m-;i++) printf("%d\n",ans[i]);

     return ;

 }

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2194

题目大意：请计算C[k]=sigma(a[i]*b[i-k]) 其中 k < = i < n ，并且有 n < = 10 ^ 5。 a,b中的元素均为小于等于100的非负整数。

做法：考虑把b数组翻转，Ck的计算就成为了裸的卷积，对于这种题目，翻转是个重要的手段。

相关文章