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
去您的萌新