钉子精神
查看原帖
钉子精神
200044
JS_TZ_ZHR楼主2020/11/3 22:17

为什么最后

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));
}
2020/11/3 22:17
加载中...