代码

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,sse3,sse4,popcnt")

#include <bits/stdc++.h>

using namespace std;

namespace fft {

    class cmplx {
       public:
        double a, b;
        cmplx() { a = 0.0, b = 0.0; }
        cmplx(double na, double nb = 0.0) { a = na, b = nb; }
        const cmplx operator+(const cmplx& c) {
            return cmplx(a + c.a, b + c.b);
        }
        const cmplx operator-(const cmplx& c) {
            return cmplx(a - c.a, b - c.b);
        }
        const cmplx operator*(const cmplx& c) {
            return cmplx(a * c.a - b * c.b, a * c.b + b * c.a);
        }
        double magnitude() { return sqrt(a * a + b * b); }
        void print() { cout << "(" << a << ", " << b << ")\n"; }
    };

    const double PI = acos(-1);

    class fft {
       public:
        vector<cmplx> data, roots;
        vector<int32_t> rev;
        int32_t n, s;

        void setSize(int32_t ns) {
            s = ns;
            n = (1 << s);
            int32_t i, j;
            rev = vector<int32_t>(n);
            data = vector<cmplx>(n);
            roots = vector<cmplx>(n + 1);
            for (i = 0; i < n; ++i) {
                for (j = 0; j < s; ++j) {
                    if (i & (1 << j)) {
                        rev[i] += (1 << (s - j - 1));
                    }
                }
            }
            roots[0] = cmplx(1);
            cmplx mult = cmplx(cos(2 * PI / n), sin(2 * PI / n));
            for (i = 1; i <= n; ++i) {
                roots[i] = roots[i - 1] * mult;
            }
        }

        void bitReverse(vector<cmplx>& arr) {
            vector<cmplx> temp(n);
            int32_t i;
            for (i = 0; i < n; ++i) temp[i] = arr[rev[i]];
            for (i = 0; i < n; ++i) arr[i] = temp[i];
        }

        void transform(bool inverse = false) {
            bitReverse(data);
            int32_t i, j, k;
            for (i = 1; i <= s; ++i) {
                int32_t m = (1 << i), md2 = m >> 1;
                int32_t start = 0, increment = (1 << (s - i));
                if (inverse) {
                    start = n;
                    increment *= -1;
                }
                cmplx t, u;
                for (k = 0; k < n; k += m) {
                    int32_t index = start;
                    for (j = k; j < md2 + k; ++j) {
                        t = roots[index] * data[j + md2];
                        index += increment;
                        data[j + md2] = data[j] - t;
                        data[j] = data[j] + t;
                    }
                }
            }
            if (inverse) {
                for (int32_t i = 0; i < n; ++i) {
                    data[i].a /= n;
                    data[i].b /= n;
                }
            }
        }

        static vector<int32_t> convolution(vector<int32_t>& a,
                                           vector<int32_t>& b) {
            int32_t alen = a.size();
            int32_t blen = b.size();
            int32_t resn = alen + blen - 1;
            int32_t s = 0, i;
            while ((1 << s) < resn) ++s;
            int32_t n = 1 << s;

            fft pga, pgb;
            pga.setSize(s);
            for (i = 0; i < alen; ++i) pga.data[i] = cmplx(a[i]);
            for (i = alen; i < n; ++i) pga.data[i] = cmplx(0);
            pga.transform();

            pgb.setSize(s);
            for (i = 0; i < blen; ++i) pgb.data[i] = cmplx(b[i]);
            for (i = blen; i < n; ++i) pgb.data[i] = cmplx(0);
            pgb.transform();

            for (i = 0; i < n; ++i) pga.data[i] = pga.data[i] * pgb.data[i];
            pga.transform(true);
            vector<int32_t> result(resn);
            for (i = 0; i < resn; ++i)
                result[i] = (int32_t)(pga.data[i].a + 0.5);

            int32_t actualSize = resn - 1;
            while (~actualSize && result[actualSize] == 0) --actualSize;
            if (actualSize < 0) actualSize = 0;
            result.resize(actualSize + 1);
            return result;
        }
    };
}  // namespace fft

namespace IO {
    constexpr bool UNSAFE = false;
    constexpr int GLOB_BUF_SIZE = 1 << 15;
#ifndef DEBUG
    #define CHANGE_DEFAULT_STREAMS
    static struct FastInput {
        FastInput() {
            if constexpr (UNSAFE) {
                chars_read = fread(buf, 1, BUF_SIZE, in);
                buf_pos = 0;
                buf[0] = (chars_read == 0 ? -1 : buf[0]);
            }
        }
        static constexpr int BUF_SIZE = GLOB_BUF_SIZE;
        char buf[BUF_SIZE];
        size_t chars_read = 0;
        size_t buf_pos = 0;
        FILE* in = stdin;
        char cur = 0;
        inline char get_char() {
            if constexpr (!UNSAFE) {
                if (buf_pos >= chars_read) {
                    chars_read = fread(buf, 1, BUF_SIZE, in);
                    buf_pos = 0;
                    buf[0] = (chars_read == 0 ? -1 : buf[0]);
                }
            }
            return cur = buf[buf_pos++];
        }
        template <typename T>
        inline FastInput* tie(T) {
            return this;
        }
        inline void sync_with_stdio(bool) {}
        inline explicit operator bool() { return cur != -1; }
        inline static bool is_blank(char c) { return c <= ' '; }
        inline bool skip_blanks() {
            while (is_blank(cur) && cur != -1) get_char();
            return cur != -1;
        }
        inline FastInput& operator>>(char& c) {
            skip_blanks();
            c = cur;
            return *this;
        }
        inline FastInput& operator>>(std::string& s) {
            if (skip_blanks()) {
                s.clear();
                do {
                    s += cur;
                } while (!is_blank(get_char()));
            }
            return *this;
        }
        template <typename T>
        inline FastInput& read_integer(T& n) {
            // unsafe, doesn't check that characters are actually digits
            n = 0;
            if (skip_blanks()) {
                int sign = +1;
                if (cur == '-') {
                    sign = -1;
                    get_char();
                }
                do {
                    n += n + (n << 3) + cur - '0';
                } while (!is_blank(get_char()));
                n *= sign;
            }
            return *this;
        }
        template <typename T>
        inline typename std::enable_if<std::is_integral<T>::value,
                                       FastInput&>::type
        operator>>(T& n) {
            return read_integer(n);
        }
    #if !defined(_WIN32) || defined(_WIN64)
        inline FastInput& operator>>(__int128& n) { return read_integer(n); }
    #endif
        template <typename T>
        inline typename std::enable_if<std::is_floating_point<T>::value,
                                       FastInput&>::type
        operator>>(T& n) {
            // not sure if really fast, for compatibility only
            n = 0;
            if (skip_blanks()) {
                std::string s;
                (*this) >> s;
                sscanf(s.c_str(), "%lf", &n);
            }
            return *this;
        }
    } fast_input;
    #define cin IO::fast_input
    static struct FastOutput {
        static constexpr int BUF_SIZE = GLOB_BUF_SIZE;
        char buf[BUF_SIZE];
        size_t buf_pos = 0;
        static constexpr int TMP_SIZE = GLOB_BUF_SIZE;
        char tmp[TMP_SIZE];
        FILE* out = stdout;
        inline void put_char(char c) {
            buf[buf_pos++] = c;
            if (buf_pos == BUF_SIZE) {
                fwrite(buf, 1, buf_pos, out);
                buf_pos = 0;
            }
        }
        ~FastOutput() { fwrite(buf, 1, buf_pos, out); }
        inline FastOutput& operator<<(char c) {
            put_char(c);
            return *this;
        }
        inline FastOutput& operator<<(const char* s) {
            while (*s) put_char(*s++);
            return *this;
        }
        inline FastOutput& operator<<(const std::string& s) {
            for (auto x : s) put_char(x);
            return *this;
        }
        template <typename T>
        inline char* integer_to_string(T n) {
            // beware of TMP_SIZE
            char* p = tmp + TMP_SIZE - 1;
            if (n == 0)
                *--p = '0';
            else {
                bool is_negative = false;
                if (n < 0) {
                    is_negative = true;
                    n = -n;
                }
                while (n > 0) {
                    *--p = (char)('0' + n % 10);
                    n /= 10;
                }
                if (is_negative) *--p = '-';
            }
            return p;
        }
        template <typename T>
        inline typename std::enable_if<std::is_integral<T>::value, char*>::type
        stringify(T n) {
            return integer_to_string(n);
        }
    #if !defined(_WIN32) || defined(_WIN64)
        inline char* stringify(__int128 n) { return integer_to_string(n); }
    #endif
        template <typename T>
        inline typename std::enable_if<std::is_floating_point<T>::value,
                                       char*>::type
        stringify(T n) {
            sprintf(tmp, "%.17f", n);
            return tmp;
        }
        template <typename T>
        inline FastOutput& operator<<(const T& n) {
            auto p = stringify(n);
            for (; *p != 0; p++) put_char(*p);
            return *this;
        }
    } fast_output;
    #define cout IO::fast_output
#endif
}  // namespace IO

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    vector<int32_t> a(n + 1), b(m + 1);
    for (auto& x : a) cin >> x;
    for (auto& x : b) cin >> x;
    int cnt = 0;
    for (auto x : fft::fft::convolution(a, b)) cout << x << ' ', cnt++;
    while (cnt <= n + m) cout << 0 << ' ', cnt++;
    cout << '\n';
    return 0;
}

评测结果