AffineRing @ 2020-11-17 21:21:12
RT三角形。
//38 lines of WA_code
#include<bits/stdc++.h>
using namespace std;
const long double Pi=acos(-1);
long long n,m,pp,tr[2700000];
struct CP{
CP (long double xx=0,long double yy=0){x=xx,y=yy;}long double x,y;
CP operator + (CP const &B) const {return CP(x+B.x,y+B.y);}
CP operator - (CP const &B) const {return CP(x-B.x,y-B.y);}
CP operator * (CP const &B) const {return CP(x*B.x-y*B.y,x*B.y+y*B.x);}
}f[2700000],g[2700000];
void fft(CP *f,bool flag){
for(long long i=0;i<n;i++)
if(i<tr[i])swap(f[i],f[tr[i]]);
for(long long p=2;p<=n;p<<=1){
long long len=p>>1;
CP tG(cos(2*Pi/p),sin(2*Pi/p));
if(!flag)tG.y*=-1;
for(long long k=0;k<n;k+=p){
CP buf(1,0);
for(long long l=k;l<k+len;l++){
CP tt=buf*f[len+l];
f[len+l]=f[l]-tt,f[l]=f[l]+tt,buf=buf*tG;
}
}
}
}
int main(){
cin>>n>>m>>pp;
for(long long i=0;i<=n;i++)cin>>f[i].x;
for(long long i=0;i<=m;i++)cin>>g[i].x;
for(m+=n,n=1;n<=m;n<<=1);
for(long long i=0;i<n;i++)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
fft(f,1);fft(g,1);
for(long long i=0;i<n;i++)f[i]=f[i]*g[i];
fft(f,0);
for(long long i=0;i<=m;++i)cout<<((long long)(f[i].x/n+0.5))%pp<<" ";
return 0;
}
为何全WA,我认为这没有问题(至少部分分),然后一分也没有……什么原因啊
by Rui_R @ 2020-11-17 21:23:15
@KDL_56iNv02 我寻思它也没说给你部分分啊?
by AffineRing @ 2020-11-17 21:24:08
@Rui_R 我寻思我的输出应该是没有问题的
by Remake_ @ 2020-11-17 21:24:43
@KDL_56iNv02
FFT不适用任意模数的啊
by AffineRing @ 2020-11-17 21:26:32
@Miracle_Creator 在没模的时候输出不是对的吗……为啥按照题意模了之后就全错啦
by Rui_R @ 2020-11-17 21:27:27
@KDL_56iNv02 我寻思它系数是1e9,你中途运算位数不得上天,这肯定会掉精度掉的很严重的啊,要把系数拆开来做
by qwqqwq_qwqqwq @ 2020-11-17 21:28:37
运算过程中系数爆精度了
by Rui_R @ 2020-11-17 21:29:01
@KDL_56iNv02 FFT 中途那么多 double 和三角函数,带有误差,系数到1e9了误差过大肯定会出事的。
by AffineRing @ 2020-11-17 21:29:10
@Rui_R 谢谢