社区讨论
神奇的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 条回复,欢迎继续交流。
正在加载回复...