竞赛讨论区 > 求教教为啥FFT过不去多项式乘法啊
头像
Vsinger_洛天依
发布于 02-16 10:05
+ 关注

求教教为啥FFT过不去多项式乘法啊

rt,我要恼了怎么看都是没啥问题的啊,样例可过但是交上去就死了

const int mod1=998244353,mod2=1e9+7,mod3=1e9+9;
const double PI=acos(-1);
struct Complex{
    double x,y;
    Complex operator+(const Complex&t)const{
        return {x+t.x , y+t.y};
    } 
    Complex operator-(const Complex&t)const{
        return {x-t.x,y-t.y};
    }
    Complex operator*(const Complex&t)const{
        return {x*t.x-y*t.y,x*t.y+y*t.x};
    }
}a[N],b[N];
int rev[N],bit,tot;
int n,m;
void fft(Complex *a,int inv){
    for(register int i=0;i<tot;i++)
        if(i<rev[i])
            swap(a[i],a[rev[i]]);
    for(register int mid=1;mid<tot;mid<<=1){
        auto w1=Complex({cos(PI/mid),inv*sin(PI/mid)});
        for(int i=0;i<tot;i+=mid*2){
            auto wk=Complex({1,0});
            for(int j=0;j<mid;j++,wk=wk*w1){
                auto x=a[i+j],y=wk*a[i+j+mid];
                a[i+j]=x+y,a[i+j+mid]=x-y;
            }
        }
    }
}
signed main(){
    // fire();
    cin>>n>>m;
    int q;
    for(register int i=0;i<=n;i++) cin>>q,a[i].x=q;
    for(register int i=0;i<=m;i++) cin>>q,b[i].x=q;
    while((1<<bit)<n+m+1) bit++;
    tot=1<<bit;
    for(register int i=0;i<tot;i++)
        rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
    fft(a,1),fft(b,1);
    for(register int i=0;i<tot;i++)
        a[i]=a[i]*b[i];
    fft(a,-1);
    for(register int i=0;i<=n+m;i++)
        cout<<((int)((a[i].x/tot+0.5)))<<' ';
}

全部评论

(1) 回帖
加载中...
话题 回帖

本文相关内容

等你来战

查看全部

热门推荐