[模板][P3803]多项式乘法

Description：

FFT真的容易忘，所以就放到上面来了

#include<bits/stdc++.h>

using namespace std;

const int mxn=4e6+5;

const double PI=acos(-1);

int n,m,l,lim=1,r[mxn];

struct cp {

    double x,y;

    cp(double xx=0,double yy=0) {x=xx,y=yy;}

    friend cp operator + (cp a,cp b) {

        return cp(a.x+b.x,a.y+b.y);

    }

    friend cp operator - (cp a,cp b) {

        return cp(a.x-b.x,a.y-b.y);

    }

    friend cp operator * (cp a,cp b) {

        return cp(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);

    }

}a[mxn],b[mxn];

void FFT(cp *p,int opt)

{

    for(int i=0;i<lim;++i)

        if(i<r[i]) swap(p[i],p[r[i]]);

    for(int mid=1;mid<lim;mid<<=1) { //枚举长度

        cp wn(cos(PI/mid),opt*sin(PI/mid));

        for(int len=mid<<1,j=0;j<lim;j+=len) { //枚举区间

            cp w(1,0);

            for(int k=0;k<mid;++k,w=w*wn) { //枚举操作的数

                cp x=p[j+k],y=w*p[j+mid+k];

                p[j+k]=x+y; p[j+mid+k]=x-y; //核心操作

            }

        }

    }

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=0;i<=n;++i) scanf("%lf",&a[i].x);

    for(int i=0;i<=m;++i) scanf("%lf",&b[i].x);

    while(lim<=n+m) lim<<=1,++l; //确定位数

    for(int i=0;i<lim;++i)

        r[i]=(r[i>>1]>>1)|((i&1)<<(l-1)); //非递归的优化

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

    for(int i=0;i<=lim;++i) a[i]=a[i]*b[i];

    FFT(a,-1);

    for(int i=0;i<=n+m;++i)

        printf("%d ",(int )(a[i].x/lim+0.5)); //IDFT之后要除以长度

    return 0;

}

巴特西

[模板][P3803]多项式乘法

Description：

最新文章

热门文章