1 条题解
-
1
#include <cstdio> #include <cmath> #include <cstring> #include <complex> using namespace std; const int N = 1e6 + 5; const double pi = 3.14159265358979; struct comp { double x, y; comp(double x = 0.0, double y = 0.0) : x(x), y(y) { } comp operator+(const comp &o) const { return comp(x + o.x, y + o.y); } comp operator-(const comp &o) const { return comp(x - o.x, y - o.y); } comp operator*(const comp &o) const { return comp(x * o.x - y * o.y, x * o.y + y * o.x); } }; comp _x1[N], _x2[N]; char s1[N], s2[N]; int ans[N], rev[N], len = 1; void fft(comp y[], int op) { for (int i = 0; i < len; ++i) if (i < rev[i]) swap(y[i], y[rev[i]]); for (int h = 2; h <= len; h <<= 1) { comp om(cos(2 * pi / h), sin(op * 2 * pi / h)); for (int j = 0; j < len; j += h) { comp w(1, 0); for (int k = j; k < j + h / 2; ++k) { comp u = y[k]; comp t = w * y[k + h / 2]; y[k] = u + t; y[k + h / 2] = u - t; w = w * om; } } } if (op == -1) for (int i = 0; i < len; ++i) y[i].x /= (double)len, y[i].y /= (double)len; } int main() { int n, m; scanf("%d%d", &n, &m); while (len <= n + m) len <<= 1; for (int i = 0; i <= n; ++i) { int x; scanf("%d", &x); _x1[i].x = double(x); } for (int i = 0; i <= m; ++i) { int x; scanf("%d", &x); _x2[i].x = double(x); } for (int i = 0; i < len; ++i) { rev[i] = rev[i >> 1] >> 1; if (i & 1) rev[i] |= len >> 1; } fft(_x1, 1); fft(_x2, 1); for (int i = 0; i < len; ++i) _x1[i] = _x1[i] * _x2[i]; fft(_x1, -1); for (int i = 0; i < len; ++i) ans[i] = int(_x1[i].x + 0.5); for (int i = 0; i <= n + m; ++i) printf("%d ", ans[i]); }
- 1
信息
- ID
- 5539
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者