代码

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
typedef double db;
const int maxn = 1000010;
const db Pi = acos(-1.0);
struct com {
    db r, i;
    com(db r_ = 0, db i_ = 0) {
        r = r_, i = i_;
    }
};
com operator + (const com &a, const com &b) {
    return com(a.r + b.r, a.i + b.i);
}
com operator - (const com &a, const com &b) {
    return com(a.r - b.r, a.i - b.i);
}
com operator * (const com &a, const com &b) {
    return com(a.r * b.r - a.i * b.i, a.r * b.i + a.i * b.r);
}
int rev[(1 << 21) + 10];
com W[(1 << 21) + 10];
void fft(com *f, int n, int op) {
    for (int i = 0; i < n; i ++) {
        if (i < rev[i]) {
            swap(f[i], f[rev[i]]);
        }
    }
    for (int mid = 1, l = 2; mid < n; mid <<= 1, l <<= 1) {
        for (int i = 0; i < n; i += l) {
            for (int j = 0; j < mid; j ++) {
                com w(W[n / mid * j].r, W[n / mid * j].i * op);
                com x = f[i | j], y = w * f[i | j | mid];
                f[i | j] = x + y;
                f[i | j | mid] = x - y;
            }
        }
    }
    if (op == -1) {
        for (int i = 0; i < n; i ++) {
            f[i].r /= n;
            f[i].i /= n;
        }
    }
}
com F[(1 << 21) + 10], G[(1 << 21) + 10];
int main () {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0, c = 0; i <= n; i ++) {
        scanf("%d", &c);
        F[i].r = c;
    }
    for (int i = 0, c = 0; i <= m; i ++) {
        scanf("%d", &c);
        F[i].i = c;
    }
    int lim = 1, k = 0;
    while (lim <= (n + m)) {
        lim <<= 1;
        k ++;
    }
    for (int i = 0; i < lim; i ++) {
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (k - 1));
        W[i] = com(cos(Pi / lim * i), sin(Pi / lim * i));
    }
    fft(F, lim, 1);
    for (int i = 0; i < lim; i ++) {
        F[i] = F[i] * F[i];
    }
    fft(F, lim, -1);
    for (int i = 0; i <= (n + m); i ++) {
        printf("%d ", (int) (F[i].i / 2 + 0.5));
        // printf("%lf ", F[i].r);
    }
    return 0;
}

评测结果