话说,测试点都是对的为啥爆零
查看原帖
话说,测试点都是对的为啥爆零
206423
焚魂楼主2021/12/2 16:50

还在学简单的fft,ac没想过但是wa倒是没想到,而且全错,下载数据点发现输出都一样(?)这是为什么呢

#include<iostream>
#include<cstdio>
#include<cstdio>
#include<cmath>
#define Maxn 13500000

using namespace std;

long long n,m;
long long limit = 1;
const double Pi = acos(-1.0);

struct cp {
	double x,y;
	cp (double xx = 0,double yy = 0) {
		x = xx;
		y = yy;
	}
}a[Maxn],b[Maxn];
cp operator + (cp a,cp b) {
	return cp(a.x + b.x,a.y + b.y);
}
cp operator - (cp a,cp b) {
	return cp(a.x - b.x,a.y - b.y);
}
cp operator * (cp a,cp b) {
	return cp(a.x*b.x - a.y*b.y,a.x*b.y + a.y*b.x);
}

void fft(long long limit,cp *a,long long type) {
	if(limit == 1)
		return;
		
	cp a1[limit>>1],b1[limit>>1];
	for(long long i = 0;i <= limit;i+=2)
		a1[i >> 1] = a[i],b1[i >> 1] = a[i+1];
		
	fft(limit>>1,a1,type);
	fft(limit>>1,b1,type);
	
	cp Wn = cp(cos(2.0*Pi/limit),type * sin(2.0*Pi/limit)),w = cp(1,0);
	for(long long i = 0;i < (limit>>1);i++,w = w*Wn) {
		cp t = w * b1[i];
		a[i] = a1[i] + t;
		a[i+(limit>>1)] = a1[i] - t;
	}
}

int main() {
	cin >> n >> m;
	for(long long i = 0;i <= n;i++) cin >> a[i].x;
	for(long long j = 0;j <= m;j++) cin >> b[j].x;
	while(limit <= n+m)
		limit <<= 1;
		
	fft(limit,a,1);
	fft(limit,b,1);
	
	for(long long i = 0;i <= limit;i++)
		a[i] = a[i] * b[i];
		
	fft(limit,a,-1);
	
	for(long long i = 0;i <= n+m;i++) {
		printf("%d ",(long long)(a[i].x/limit + 0.49));
	}
	
	return 0;
}
2021/12/2 16:50
加载中...