多项式萌新求助FFT
查看原帖
多项式萌新求助FFT
294736
bovine__kebi楼主2020/5/18 19:14

RT,一直输出00/kel

#pragma GCC optimize("Ofast","-funroll-loops","-fdelete-null-pointer-checks")
#pragma GCC target("ssse3","sse3","sse2","sse","avx2","avx")
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
const double pi=acos(-1.0);
typedef long long ll;
struct node
{
    double re,im;
    node operator+(const node&x)const{
        return(node){re+x.re,im+x.im};
    }
    node operator-(const node&x)const{
        return(node){re-x.re,im-x.im};
    }
    node operator*(const node&x)const{
        return(node){re*x.re-im*x.im,re*x.im+im*x.re};
    }
}a[maxn],b[maxn];
int lim,l,r[maxn];
inline void swap(node&a,node&b) {
    node tmp=a; a=b,b=tmp;
}
inline void get(int n)
{
    lim=1;l=0;
    while(lim<=n)
    {
        lim<<=1;
        l++;
    }
    for(int i=1;i<lim;i++)
    {
        r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    }
}
inline void DFT(node *a)
{
    node w,x,y,Wn;
    for(register int i=0;i<lim;i++)if(i<r[i])swap(a[i],a[r[i]]);
    for(register int i=1;i<lim;i<<=1)
    {
        Wn=(node){cos(pi/i),sin(pi/i)};
        for(register int j=0,step=i<<1;j<lim;j+=step)
        {
            w=(node){1,0};
            for(register int k=0;k<i;k++,w=w*Wn)
            {
                x=a[i+k];y=w*a[i+j+k];
                a[j+k]=x+y;a[i+j+k]=x-y;
            }
        }
    }
}
inline void IDFT(node *a)
{
    node w,x,y,Wn;
    for(register int i=0;i<lim;i++)if(i<r[i])swap(a[i],a[r[i]]);
    for(register int i=1;i<lim;i<<=1)
    {
        Wn=(node){cos(pi/i),-sin(pi/i)};
        for(register int j=0,step=i<<1;j<lim;j+=step)
        {
            w=(node){1,0};
            for(register int k=0;k<i;k++,w=w*Wn)
            {
                x=a[i+k];y=w*a[i+j+k];
                a[j+k]=x+y;a[i+j+k]=x-y;
            }
        }
    }
}
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=0;i<=n;i++)
    {
        scanf("%lf",&a[i].re);
    }
    for(int i=0;i<=m;i++)
    {
        scanf("%lf",&b[i].re);
    }
    get(n+m+2);DFT(a);DFT(b);
    for(int i=0;i<lim;i++)
    {
        a[i]=a[i]*b[i];
    }
    IDFT(a);
    for(int i=0;i<=n+m;i++)
    {
        printf("%.0lf ",a[i].re+0.01);
    }
}
2020/5/18 19:14
加载中...