FFT 求大佬查错
查看原帖
FFT 求大佬查错
90972
shitbro楼主2020/12/28 20:24
#include <cstdio>
#include <complex>

using namespace std;
const int MAX_M = 1 << 20; 

const double pi = acos(-1.0);

struct CP {
	double x,y;
	CP() {
		x = y = 0;
	}
	CP (double _x,double _y) {
		x = _x; y = _y;
	}
	CP operator + (CP const & B) const {
		return CP(B.x + x,B.y + 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,y * B.x + x * B.y);
	} 
}a[MAX_M],b[MAX_M],temp[MAX_M],ans[MAX_M];

void DFT(CP *f,int n,int rev) {
	if(n == 1) return ;
	for(int i = 0;i < n;i ++) temp[i] = f[i];
	for(int i = 0;i < n;i ++) {
		if(i & 1) f[i + n / 2] = temp[i];
		else f[i] =  temp[i];
	}
	CP *g = f,*h = f + n / 2;
	DFT(g,n / 2,rev); DFT(h,n / 2,rev);
	CP cur(1,0),step(cos(2 * pi / n),sin(2 * pi * rev / n));
	for(int k = 0;k < n / 2;k ++) {
		temp[k] = g[k] + cur * h[k];
		temp[k + n / 2] = g[k] - cur * h[k];
		cur = cur * step;
	}
	for(int i = 0;i < n;i ++) f[i] = temp[i];
} 
int main () {
	int n,m; 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 mul; for(mul = 1;mul <= n + m;) mul <<= 1;
	DFT(a,mul,1); DFT(b,mul,1);
	for(int i = 0;i < mul;i ++) ans[i] = a[i] * b[i];
	DFT(ans,mul,-1);
	for(int i = 0;i <= n + m;i ++) {
		printf("%d ",(int)(ans[i].x / mul + 0.5));
	} 
	return 0;
}
2020/12/28 20:24
加载中...