代码

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
const double PI = 3.14159265358979323846;
#define int long long
const int N = 300005;
using namespace std;
struct Complex {
    double a, b;
    Complex operator+(Complex o) const { return { a + o.a, b + o.b }; }
    Complex operator-(Complex o) const { return { a - o.a, b - o.b }; }
    Complex operator*(Complex o) const { return { a * o.a - b * o.b, a * o.b + b * o.a }; }
    Complex operator/(double o) const { return { a / o, b / o }; }
    Complex operator~() const { return { a, -b }; }
    Complex operator-() const { return { -a, -b }; }
};
Complex f[N], g[N], tmp[N];
int n, lgn, m[2], r[N];
void change(Complex x[]) {
    for (int i = 0; i < n; i++) {
        r[i] = r[i >> 1] >> 1;
        if (i & 1)
            r[i] |= (n >> 1);
    }
    for (int i = 0; i < n; i++)
        if (i < r[i])
            swap(x[i], x[r[i]]);
}
void fft(Complex t[], int on) {
    change(t);
    for (int h = 2; h <= n; h <<= 1) {
        Complex wn = { cos(2 * PI / h), sin(on * 2 * PI / h) };
        for (int j = 0; j < n; j += h) {
            Complex w = { 1, 0 };
            for (int k = j; k < j + h / 2; k++) {
                Complex u = t[k], tmp = w * t[k + h / 2];
                t[k] = u + tmp, t[k + h / 2] = u - tmp;
                w = w * wn;
            }
        }
    }
}
main() {
	ios::sync_with_stdio(0), cin.tie(0);
    cin >> m[0] >> m[1];
    m[0]++, m[1]++;
    for (int i = 0, x; i < m[0]; i++) cin >> x, f[i].a = x;
    for (int i = 0, x; i < m[1]; i++) cin >> x, f[i].b = x;
    lgn = __lg(m[0] + m[1] - 2) + 1;
    n = 1 << lgn;
    fft(f, 1);
    for (int i = 0; i < n; i++) f[i] = f[i] * f[i];
    fft(f, -1);
    for (int i = 0; i < m[0] + m[1] - 1; i++) printf("%lld ", (int)round(f[i].b / (2 * n)));
putchar(10);
}

评测结果