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
您这个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::sin
和sin
应该没区别吧,都是cmath里的函数,而且std::sin
的定义大概是这样的(如果我没记错的话)
namespace std
{
using ::sin;
}
by SovietPower✨ @ 2019-05-05 10:42:53
std::sin
的精度确实比sin
高