萌新刚学OI,求助MTT!

P4245 【模板】任意模数多项式乘法

Qiuly @ 2019-03-16 11:12:35

RT,一半A一半WA,于是猜想后面的WA或许是精度的原因,但是将FFT换成long double 后还是WA啊QwQ.....肿么办啊。

求大佬的帮助QvQ

#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>

const int N=4e5+2;
const int BLOCK=32768;

#define PI 3.1415926535898
typedef long long ll;

int filp[N],Ans[N],limit=1,n,m,p;
struct complex{complex(long double a=0,long double b=0){x=a,y=b;}long double x,y;};
complex operator + (complex a,complex b){return complex(a.x+b.x,a.y+b.y);}
complex operator - (complex a,complex b){return complex(a.x-b.x,a.y-b.y);}
complex operator * (complex a,complex b){return complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
complex A1[N],B1[N],A2[N],B2[N],X[N];

inline void FFT(complex *f,short inv){
    for(int i=0;i<limit;++i)if(i<filp[i])std::swap(f[i],f[filp[i]]);
    for(int p=2;p<=limit;p<<=1){
        int len=p>>1;
        complex tmp=complex(cos(PI/len),inv*sin(PI/len));
        for(int k=0;k<limit;k+=p){
            complex buf=complex(1,0);
            for(int l=k;l<k+len;++l,buf=buf*tmp){
                complex t=f[l+len]*buf;
                f[l+len]=f[l]-t,f[l]=f[l]+t;
            }           
        }
    }return;
}

inline void solve(complex *a,complex *b,int res){
    for(int i=0;i<limit;++i)X[i]=a[i]*b[i];
    FFT(X,-1);
    for(int i=0;i<=n+m;++i)(Ans[i]+=(ll)(X[i].x/limit+0.5)%p*res%p)%=p;
}
inline void MTT(complex *a,complex *b,complex *c,complex *d){
    FFT(a,1),FFT(c,1),FFT(b,1),FFT(d,1);
    solve(a,c,BLOCK*BLOCK%p);solve(a,d,BLOCK%p);
    solve(c,b,BLOCK%p);solve(b,d,1);
}

int main(){
    scanf("%d%d%d",&n,&m,&p);
    for(int i=0,x;i<=n;++i)
        scanf("%d",&x),A1[i]=x/BLOCK,B1[i]=x%BLOCK;
    for(int i=0,x;i<=m;++i)
        scanf("%d",&x),A2[i]=x/BLOCK,B2[i]=x%BLOCK;
    while(limit<(n+m))limit<<=1;
    for(int i=0;i<limit;++i)filp[i]=(filp[i>>1]>>1)|((i&1)?limit>>1:0);
    MTT(A1,B1,A2,B2);
    for(int i=0;i<=n+m;++i)
        printf("%d ",Ans[i]);
    printf("\n");
    return 0;
}

by ezoixx118 @ 2019-03-16 11:13:35

新人学mtt orz


by ezoixx118 @ 2019-03-16 11:14:07

我只会三模数


by 142857cs @ 2019-03-16 11:14:11

没办法了


by 142857cs @ 2019-03-16 11:14:28

新人学mtt orz++


by Qiuly @ 2019-03-16 11:14:33

QwQ然而板子打错了......并且差不出错QwQ


by 142857cs @ 2019-03-16 11:14:53

我也只会三模数


by Qiuly @ 2019-03-16 11:14:53

Orz大佬们帮帮忙吧QwQ


by Qiuly @ 2019-03-16 11:15:29

MTT比NTT合并简单些啊QwQ.....


by 开始新的记忆 @ 2019-03-16 11:26:32

去您的萌新


by 142857cs @ 2019-03-16 11:27:35

去您的萌新


| 下一页