用了非递归的版本(二进制翻转) , 手写的复数 , 还是T了 , 有没有带佬帮忙看看常数大在哪里了啊qaq
这是评测记录
#include <bits/stdc++.h>
using namespace std;
const double PI = acos(-1);
const int maxn = 2345678;
struct cp {
double x, y;
cp() { x = y = 0; }
cp(double X, double Y) : x(X), y(Y) {}
cp operator + (const cp& o) const {
return cp(x + o.x, y + o.y);
}
cp operator - (const cp& o) const {
return cp(x - o.x, y - o.y);
}
void operator *= (const cp& o) {
double tx = x * o.x - y * o.y;
y = x * o.y + y * o.x;
x = tx;
}
void operator /= (const int& n) {
x /= n; y /= n;
}
}a[maxn], b[maxn];
inline int flip(int &x) {
int t = 1, rs = 0;
while(t < x) t <<= 1, ++rs;
x = t;
return rs;
}
void dft(cp *a, int n, int w2) {
cp t[n];
for(int i = 0; i < n; ++i) {
int p = 0;
for(int cnt = 0, tmp = i; cnt < w2; ++cnt, tmp >>= 1) p <<= 1, p += tmp & 1;
t[p] = a[i];
}
for(int m = 2; m <= n; m <<= 1) {
int hf = m >> 1;
for(int i = 0; i < n; i += m)
for(int k = 0; k < hf; ++k) {
cp omg = cp(cos(2*PI*k/m), sin(2*PI*k/m));
omg *= t[i+k+hf];
t[i+k+hf] = t[i+k] - omg;
t[i+k] = t[i+k] + omg;
}
}
for(int i = 0; i < n; ++i) a[i] = t[i];
}
void idft(cp *a, int n, int w2) {
reverse(a + 1, a + n);
dft(a, n, w2);
for(int i = 0; i < n; ++i) a[i] /= n;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
cin >> n >> m;
for(int i = 0; i <= n; ++i) cin >> a[i].x;
for(int i = 0; i <= m; ++i) cin >> b[i].x;
int len = n + m + 1;
int w2 = flip(len);
dft(a, len, w2);
dft(b, len, w2);
for(int i = 0; i < len; ++i) a[i] *= b[i];
idft(a, len, w2);
for(int i = 0; i <= n + m; ++i) cout << (int)(a[i].x + 0.5) << ' ';
cout << endl;
return 0;
}