为什么最后
a[i].x
要取绝对值才可以过啊?看题解没有发现问题,但别人没有取绝对值
#include<bits/stdc++.h>
using namespace std;
int n,m,sum[2100005],num;
double Pi=3.1415;
struct node {
double x,y;
node(double _x=0,double _y=0) {
x=_x,y=_y;
}
} a[2100005],b[2100005];
node operator+(node a,node b) {
return node(a.x+b.x,a.y+b.y);
}
node operator-(node a,node b) {
return node(a.x-b.x,a.y-b.y);
}
node operator*(node a,node b) {
return node(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);
}
inline void FFT(int len,node *s,int opt) {
for(int i=0; i<len; i++)if(i<sum[i])swap(s[i],s[sum[i]]);
for(int i=1;i<len;i<<=1){
node W=node(cos(Pi/(double)i),(double)opt*sin(Pi/(double)i));
for(int j=0;j<len;j+=(i<<1)){
node w=node(1.0,0.0);
for(int k=0;k<i;k++,w=w*W){
node t1=w*s[i+j+k],t2=s[j+k];
s[j+k]=t1+t2;
s[i+j+k]=t1-t2;
}
}
}
}
int main() {
scanf("%d%d",&n,&m);
for(int i=0; i<=n; i++)scanf("%lf",&a[i].x);
for(int i=0; i<=m; i++)scanf("%lf",&b[i].x);
int len=1;
while(len<=n+m)len<<=1,num++;
for(int i=0; i<len; i++)sum[i]=(sum[i>>1]>>1)|((i&1)<<(num-1));
FFT(len,a,1);
FFT(len,b,1);
for(int i=0; i<=len; i++)a[i]=b[i]*a[i];
FFT(len,a,-1);
for(int i=0; i<=n+m; i++)printf("%d ",(int)(abs(a[i].x)/len+0.5));
}