代码

//author: ycp | https://ycpedef.github.io
//#pragma GCC diagnostic error "-std=c++11"
//#pragma GCC optimize(2)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdarg>
#include <cmath>
#include <complex>
#define debug(x) cerr << #x << " = " << x << endl
#define debugf(...) fprintf(stderr, __VA_ARGS__)
#define debugs(x) fputs(x"\n", stderr)
using namespace std;
template <class T> bool cmax(T &a, T b) { return b > a ? (a = b, 1) : 0; }
template <class T> bool cmin(T &a, T b) { return b < a ? (a = b, 1) : 0; }
template <class T> void read(T &a) {
    a = 0; char c = getchar(); int f = 0;
    while (!isdigit(c)) { f ^= c == '-',  c = getchar(); }
    while (isdigit(c)) { a = a * 10 + (c ^ 48),  c = getchar(); }
    a *= f ? -1 : 1;
}
struct Fastin {
    template <class T> Fastin& operator >> (T &x) {read(x); return *this;}
} fastin;

template <typename T>
class Complex {
    T a, b;
    public:
    Complex(T new_a = 0., T new_b = 0.): a(new_a), b(new_b) {}
    Complex(const Complex<T> &cur): a(cur.a), b(cur.b) {}
    friend Complex<T> operator - (Complex<T> z1, Complex<T> z2) {
        return Complex(z1.a - z2.a, z1.b - z2.b);
    }
    friend Complex<T> operator + (Complex<T> z1, Complex<T> z2) {
        return Complex(z1.a + z2.a, z1.b + z2.b);
    }
    friend Complex<T> operator * (Complex<T> z1, Complex<T> z2) {
        return Complex(z1.a * z2.a - z1.b * z2.b, z1.b * z2.a + z1.a * z2.b);
    }
    T real() { return a; }
    T imag() { return b; }
    void real(T cur) { a = cur; }
    void imag(T cur) { b = cur; }
    void print() { cout << a << " + " << b << "i" << endl; }
};

#define YCP

#ifdef YCP
typedef Complex<double> comp;
#else
typedef complex<double> comp;
#endif

const double pi = acos(-1);

const int MAXN = 4e6 + 10;

void change(comp f[], int len) {
    static int rev[MAXN];
    for (int i = 0; i < len; i++) {
        rev[i] = rev[i >> 1] >> 1;
        rev[i] |= (i & 1) * (len >> 1);
        //debugf("change from rev[%d](%d) to rev[%d](%d)\n", i >> 1, rev[i >> 1], i, rev[i]);
    }
    //for (int i = 0; i < len; i++) {
    //    debugf("rev[%d] = %d\n", i, rev[i]);
    //}
    for (int i = 0; i < len; i++) {
        if (i < rev[i]) {
            swap(f[i], f[rev[i]]);
        }
    }
    //for (int i = 0; i < len; i++) {
    //    debugf("rev[%d] = %d\n", i, rev[i]);
    //}
    //debugf("\n");
}

void fft(comp f[], int len, int mode) {
    change(f, len);
    for (int n = 2; n <= len; n <<= 1) {
        comp wn(cos(2 * pi / n), sin(2 * pi * mode / n));
        for (int st = 0; st < len; st += n) {
            comp cur(1, 0);
            for (int k = st; k < st + n / 2; k++) {
                comp u = f[k], v = cur * f[k + n / 2];
                f[k] = u + v, f[k + n / 2] = u - v;
                cur = cur * wn;
            }
        }
    }
    if (mode == -1) {
        for (int i = 0; i < len; i++) {
            f[i].real(f[i].real() / len);
        }
    }
}

int n, m, len;
comp f[MAXN], g[MAXN], res[MAXN];

int main() {
#ifdef LOCAL
    freopen("P3803_1.in", "r", stdin);
#endif
    comp test(2, 3);
    //test.print();
    comp test2(3, 1);
    comp test3(test * test2);
    comp test4(test - test2);
    //test3.print();
    //test4.print();
    //debugf("compiled on [%s]\n", __TIME__);
    fastin >> n >> m;
    len = 1;
    while (len < n * 2 || len < m * 2) len <<= 1;
    //debug(len);
    for (int i = 0, x; i <= n; i++) {
        fastin >> x;
        f[i] = comp((double)x);
    }
    for (int i = 0, x; i <= m; i++) {
        fastin >> x;
        g[i] = comp((double)x);
    }
    fft(f, len, 1);
    fft(g, len, 1);
    for (int i = 0; i <= len; i++) {
        res[i] = f[i] * g[i];
    }
    fft(res, len, -1);
    for (int i = 0; i <= n + m; i++) {
        printf("%lld ", (long long)round(res[i].real()));
    }
    return 0;
}

评测结果