萌新刚学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 诗乃 @ 2019-03-16 11:28:54

去您的萌新


by 萌田薰子 @ 2019-03-16 11:31:01

去您的萌新

数论实在帮不到


by CaptainSlow @ 2019-03-16 11:34:48

您这个\pie精度会高才怪。 另外,用std::sin取代sin精度更高。


by Qiuly @ 2019-03-16 11:37:30

@CaptainSlow

PI是这样吗QwQ?

const long double PI=acos(-1);

by Qiuly @ 2019-03-16 11:38:21

cos的话要不要换成std::cos啊QwQ


by Qiuly @ 2019-03-16 11:44:36

@CaptainSlow

AC了AC了!谢谢大佬提醒!


by Qiuly @ 2019-03-16 11:44:51

谢谢大家!此贴终结!


by o_QAQ_o @ 2019-03-16 13:11:58

(Mettaton:什么鬼,喊我干啥)


by zhanghengrui @ 2019-03-27 21:33:17

@CaptainSlow std::sinsin应该没区别吧,都是cmath里的函数,而且std::sin的定义大概是这样的(如果我没记错的话)

namespace std
{
    using ::sin;
}

by SovietPower✨ @ 2019-05-05 10:42:53

std::sin的精度确实比sin


上一页 |