代码

#include <bits/stdc++.h>
using namespace std;

struct Type
{
    double a, b;
    Type operator + (const Type &x) const { return (Type){a + x.a, b + x.b}; }
    Type operator - (const Type &x) const { return (Type){a - x.a, b - x.b}; }
    Type operator * (const Type &x) const { return (Type){a * x.a - b * x.b, a * x.b + b * x.a}; }
};

const int N = 400007;
const double Pi = acos(-1);
int n, m1, m2;
Type f[N]; int rp[N];

void fft(int c)
{
    int i, j, k;
    for (i = 0; i < n; ++i)
        if (i < rp[i])
            swap(f[i], f[rp[i]]);
    for (i = 2; i <= n; i <<= 1)
    {
        Type tg = {cos(Pi * 2 / i), sin(Pi * 2 / i) * c};
        for (j = 0; j < n; j += i)
        {
            Type w{1, 0};
            for (k = j; k < j + i / 2; ++k, w = w * tg)
            {
                Type t1 = f[k], t2 = f[k + i / 2] * w;
                f[k] = t1 + t2, f[k + i / 2] = t1 - t2;
            }
        }
    }
}

void read(int &x)
{
    char c;
    x = 0;
    do
        c = getchar();
    while (!isdigit(c));
    while (isdigit(c))
        x = x * 10 + c - '0', c = getchar();
}

int st[37];

void write(long long x)
{
    int tot = 0;
    while (x)
        st[tot++] = x % 10, x /= 10;
    while (tot--)
        putchar(st[tot] + '0');
    putchar(' ');
}

int main()
{
    int i, x, lg = 0;
    scanf("%d%d", &m1, &m2),++m1,++m2;
    for (i = 0; i < m1; ++i)
        read(x), f[i].a = x;
    for (i = 0; i < m2; ++i)
        read(x), f[i].b = x;
    n = 1;
    while (n < m1 + m2 - 1)
        n <<= 1, ++lg;
    for (i = 0; i < n; ++i)
        rp[i] = (rp[i >> 1] >> 1) | ((i & 1) << (lg - 1));
    fft(1);
    for (i = 0; i < n; ++i)
        f[i] = f[i] * f[i];
    fft(-1);
    for (i = 0; i < m1 + m2 - 1; ++i)
        write((long long)(round(f[i].b / n) / 2));
    return 0;
}

评测结果