社区讨论

神奇的RE问题

P3803【模板】多项式乘法(FFT)参与者 5已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@lo1bsbig
此快照首次捕获于
2023/10/22 18:28
2 年前
此快照最后确认于
2023/11/02 18:49
2 年前
查看原帖
在 windows 下编译直接运行就会re,但是 Linux 下运行均无问题 (吸不吸氧结果一样)
经测试将 ans = f * g; 注释后 Windows 下可正常运行。
代码如下:
CPP
#include <bits/stdc++.h>
#define N 2097152
using namespace std;
int n, m;
const double PI = std::acos(-1);
int rev[N], lim;
struct poly {
	int len;
	complex<double> a[N];
	poly() {
		memset(a, 0, sizeof(a));
	}
	complex<double>& operator[](int t) {
		return a[t];
	}
	const complex<double>& operator[](int t) const {
		return a[t];
	}
	friend poly operator* (poly a, poly b);
}f, g, ans;
void fft(poly& a, double c) {
	for (int i = 0; i < lim; ++i) if (i < rev[i]) swap(a[i], a[rev[i]]);
	for (int i = 1; i < lim; i <<= 1) {
		complex<double> x(cos(PI / i), sin(PI / i) * c);
		for (int j = 0; j < lim; j += (i << 1)) {
			complex<double> y(1, 0);
			for (int k = 0; k < i; ++k, y = y * x) {
				auto p = a[j + k], q = y * a[j + k + i];
				a[j + k] = p + q;
				a[j + k + i] = p - q;
			}
		}
	}
}
poly operator* (poly a, poly b) {
	int l = 0;
	for (lim = 1; lim <= (a.len + b.len); lim <<= 1) ++l;
	for (int i = 0; i < lim; ++i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));
	fft(a, 1);
	fft(b, 1);
	for (int i = 0; i < lim; ++i) a[i] *= b[i];
	fft(a, -1);
	for (int i = 0; i < lim; ++i) a[i] /= lim;
	return a;
}
int main() {
	scanf("%d%d", &n, &m);
	f.len = n;
	g.len = m;
	for (int i = 0; i <= n; ++i) {
		double tmp;
		scanf("%lf", &tmp);
		f[i] = tmp;
	}
	for (int i = 0; i <= m; ++i) {
		double tmp;
		scanf("%lf", &tmp);
		g[i] = tmp;
	}
	ans = f * g;
	for (int i = 0; i <= m + n; ++i) {
		printf("%d ", int(ans[i].real() + 0.5));
	}
	return 0;
}

回复

4 条回复,欢迎继续交流。

正在加载回复...