[BZOJ]2194: 快速傅立叶之二

时间：2023-12-02 14:01:32

题目大意：给定序列a,b，求序列c满足c[k]=sigma(a[i]*b[i-k]) (k<=i<n)。（n<=10^5）

思路：观察发现就是普通的卷积反一反（翻转ab其中一个后做卷积，倒着输出即可），FFT模板复习。

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

inline int read()

{

    int x;char c;

    while((c=getchar())<''||c>'');

    for(x=c-'';(c=getchar())>=''&&c<='';)x=(x<<)+(x<<)+c-'';

    return x;

}

#define MN 262144

struct cp

{

    double r,i;

    cp(double r=,double i=):r(r),i(i){}

    cp operator+(cp b){return cp(r+b.r,i+b.i);}

    cp operator-(cp b){return cp(r-b.r,i-b.i);}

    cp operator*(cp b){return cp(r*b.r-i*b.i,r*b.i+i*b.r);}

}w[][MN+],a[MN+],b[MN+],c[MN+];

const double pi=acos(-);

int N,R[MN+];

void init(int n)

{

    for(N=;N<n;N<<=);

    int i,j,k;cp g(cos(*pi/N),sin(*pi/N));

    for(i=w[][].r=;i<N;++i)w[][i]=w[][i-]*g;

    for(i=w[][].r=;i<N;++i)w[][i]=w[][N-i];

    for(i=j=;i<N;R[++i]=j)for(k=N>>;(j^=k)<k;k>>=);

}

void fft(cp*x,int v)

{

    int i,j,k;

    for(i=j=;i<N;++i)if(i<R[i])swap(x[i],x[R[i]]);

    for(i=;i<N;i<<=)for(j=;j<N;j+=i<<)for(k=;k<i;++k)

    {

        cp p=x[i+j+k]*w[v][N/(i<<)*k];

        x[i+j+k]=x[j+k]-p;x[j+k]=x[j+k]+p;

    }

    if(v)for(i=;i<N;++i)x[i].r/=N,x[i].i/=N;

}

int main()

{

    int n=read(),i;

    for(i=;i<n;++i)a[n-i-].r=read(),b[i]=read();

    init(n<<);fft(a,);fft(b,);

    for(i=;i<N;++i)c[i]=a[i]*b[i];fft(c,);

    for(i=n;i--;)printf("%d\n",int(c[i].r+0.5));

}

相关文章