代码

/*+lmake
 * DEFINE += MDEBUG
 * STD = c++11
 */
#include <bits/stdc++.h>
#ifdef MDEBUG
#define debug(args...)                                                                             \
    {                                                                                              \
        dbg, args;                                                                                 \
        cerr << endl;                                                                              \
    }
#define massert(x) assert(x)
#else
#define debug(args...) // Just strip off all debug tokens
#define massert(x)
#endif
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
struct debugger
{
    template <typename T>
    debugger &operator,(const T &v)
    {
        cerr << v << " ";
        return *this;
    }
} dbg;
void iopen()
{
    static bool isOpen = false;
    if (!isOpen) {
        isOpen = true;
#ifdef MDEBUG
        freopen("in.txt", "r", stdin);
#endif
    }
}
template <size_t _I_Buffer_Size = 1 << 23, size_t _O_Buffer_Size = 1 << 23>
struct IO_Tp
{
    char _I_Buffer[_I_Buffer_Size];
    char *_I_pos;

    char _O_Buffer[_O_Buffer_Size];
    char *_O_pos;

    IO_Tp()
        : _I_pos(_I_Buffer)
        , _O_pos(_O_Buffer)
    {
        iopen();
        fread(_I_Buffer, 1, _I_Buffer_Size, stdin);
    }

    ~IO_Tp() { fwrite(_O_Buffer, 1, _O_pos - _O_Buffer, stdout); }

    inline bool is_digit(const char ch) { return '0' <= ch && ch <= '9'; }

    template <typename Int>
    inline IO_Tp &operator>>(Int &res)
    {
        res = 0;
        int k = 1;
        while (!is_digit(*_I_pos)) {
            if (*_I_pos == '-')
                k = -1;
            _I_pos++;
        }
        do
            (res *= 10) += (*_I_pos++) & 15;
        while (is_digit(*_I_pos));
        res *= k;
        return *this;
    }

    inline char getop()
    {
        while (!is_digit(*_I_pos))
            _I_pos++;
        return (*_I_pos++) & 15;
    }

    template <typename Int>
    inline IO_Tp &operator<<(Int n)
    {
        if (n < 0) {
            *_O_pos++ = '-';
            n = -n;
        }
        static char _buf[20];
        char *_pos(_buf);
        do
            *_pos++ = '0' + n % 10;
        while (n /= 10);
        while (_pos != _buf)
            *_O_pos++ = *--_pos;
        return *this;
    }

    inline IO_Tp &operator<<(char ch)
    {
        *_O_pos++ = ch;
        return *this;
    }
};
IO_Tp<1 << 25, 1 << 25> IO;

#define MAXN 4000000
template <typename Double>
struct Complex
{
    Double r, i;
    Complex(Double r = 0, Double i = 0)
        : r(r)
        , i(i)
    {
    }
    inline Double real() { return r; }
    inline Double imag() { return i; }
};
using complex_t = Complex<double>;
complex_t operator+(const complex_t &a, const complex_t &b)
{
    return { a.r + b.r, a.i + b.i };
}
complex_t operator-(const complex_t &a, const complex_t &b)
{
    return { a.r - b.r, a.i - b.i };
}
complex_t operator*(const complex_t &a, const complex_t &b)
{
    return { a.r * b.r - a.i * b.i, a.r * b.i + a.i * b.r };
}
complex_t a[MAXN + 10], b[MAXN + 10];
int rev[MAXN + 10];
const double pi = acos(-1);
void fft(int n, complex_t *a, int flag)
{
    for (int i = 0, j = 0; i < n; ++i) {
        if (i > j)
            swap(a[i], a[j]);
        for (int k = n >> 1; (j ^= k) < k; k >>= 1)
            ;
    }
    for (int i = 1; i < n; i *= 2) {
        int nn = i * 2;
        complex_t wn = (complex_t){ cos(2 * pi / nn), flag * sin(2 * pi / nn) };
        for (int j = 0; j < n; j += nn) {
            complex_t *a1 = a + j, *a2 = a1 + i;
            complex_t w = (complex_t){ 1, 0 };
            for (int k = 0; k < i; ++k) {
                complex_t x = a1[k], y = w * a2[k];
                a1[k] = x + y;
                a2[k] = x - y;
                w = w * wn;
            }
        }
    }
}
int main()
{
    iopen();
    int n, m;
    IO >> n >> m;
    for (int i = 0; i <= n; ++i) {
        int t;
        IO >> t;
        a[i] = complex_t(t, 0);
    }
    for (int i = 0; i <= m; ++i) {
        int t;
        IO >> t;
        b[i] = complex_t(t, 0);
    }
    LL l = 1;
    for (; l <= n + m; l *= 2)
        ;
    fft(l, a, 1);
    fft(l, b, 1);
    for (int i = 0; i <= l; ++i) {
        a[i] = a[i] * b[i];
    }
    fft(l, a, -1);
    for (int i = 0; i <= n + m; ++i) {
        IO << LL((a[i].real() / l) + 0.5) << ' ';
    }
    IO << '\n';
    return 0;
}

评测结果