代码

/* poly.cpp */
#include <bits/stdc++.h>

using i64 = long long;

constexpr int P = 998244353, primitiveRoot = 3;

struct Clock {
    std::string name;
    std::chrono::steady_clock::time_point last;
    Clock(const std::string &name_)
        : name(name_), last(std::chrono::steady_clock::now()) {}
    void step(const std::string &msg, bool update = true) {
        auto now = std::chrono::steady_clock::now();
        std::chrono::duration<double> diff = now - last;
        std::cerr << name << "(" << msg << "): " << diff.count() << std::endl;
        if (update) last = now;
    }
};

namespace Allocator {
constexpr std::size_t BufSize = 64 * 1024 * 1024;
char buf[BufSize]; std::size_t cur = 0;

template <typename T> struct FastAllocator {
    using value_type = T;
    FastAllocator() = default;
    template <typename U> constexpr FastAllocator(const FastAllocator<U> &) noexcept {}

    [[nodiscard]] T *allocate(std::size_t n) {
        if (n > (BufSize - cur) / sizeof(T))
            throw std::bad_array_new_length();
        T* p = static_cast<T*>((void *)(buf + cur));
        cur += n * sizeof(T);
        report(p, n, true);
        return p;
    }
    void deallocate(T* p, std::size_t n) noexcept {
        report(p, n, false);
    } 
    template <typename U> bool operator==(const FastAllocator<U> &) const { return true; }
    template <typename U> bool operator!=(const FastAllocator<U> &) const { return false; }
private:
    void report(T* p, std::size_t n, bool alloc) const {
        // std::cerr << "在 " << std::hex << std::showbase
        //     << reinterpret_cast<void*>(p) << std::dec
        //     << (alloc ? " 分配 " : " 解分配 ")
        //     << sizeof(T) * n << " 个字节\n";
    }
};
}
template <typename T> using Vector = std::vector<T, Allocator::FastAllocator<T>>;

template <typename T> constexpr T power(T a, i64 b) {
    T c = 1; for (; b; b /= 2, a *= a) if (b & 1) c *= a;
    return c;
}
template <int P> struct MInt {
    int x;
    constexpr MInt() : x{} {}
    constexpr MInt(i64 x_) : x{norm(x_ % getMod())} {}
    static int Mod;
    constexpr static int getMod() { return P > 0 ? P : Mod; }
    constexpr static void setMod(int Mod_) { Mod = Mod_; }
    constexpr int norm(int x) const {
        if (x < 0) x += getMod();
        if (x >= getMod()) x -= getMod();
        return x;
    }
    constexpr int val() const { return x; }
    explicit constexpr operator int() const { return x; }
    constexpr MInt operator-() const {
        MInt res; res.x = norm(getMod() - x); return res;
    }
    constexpr MInt inv() const {
        assert(x != 0);
        return power(*this, getMod() - 2);
    }
    constexpr MInt &operator+=(MInt rhs) & { return x = norm(x + rhs.x), *this; }
    constexpr MInt &operator-=(MInt rhs) & { return x = norm(x - rhs.x), *this; }
    constexpr MInt &operator*=(MInt rhs) & { return x = 1ll * x * rhs.x % getMod(), *this; }
    constexpr MInt &operator/=(MInt rhs) & { return *this *= rhs.inv(); }
    friend constexpr MInt operator+(MInt lhs, MInt rhs) { return lhs += rhs; }
    friend constexpr MInt operator-(MInt lhs, MInt rhs) { return lhs -= rhs; }
    friend constexpr MInt operator*(MInt lhs, MInt rhs) { return lhs *= rhs; }
    friend constexpr MInt operator/(MInt lhs, MInt rhs) { return lhs /= rhs; }
    friend constexpr bool operator==(MInt lhs, MInt rhs) { return lhs.val() == rhs.val(); }
    friend constexpr bool operator!=(MInt lhs, MInt rhs) { return lhs.val() != rhs.val(); }
    friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
        i64 x = 0; is >> x, a = MInt(x); return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
        return os << a.val();
    }
};

template <int P> int MInt<P>::Mod = P;
template <> int MInt<0>::Mod = 1;
template <int V, int P> constexpr MInt<P> CInv = MInt<P>(V).inv();

using Z = MInt<P>;

namespace Polynomial {
Vector<Z> roots;

void initRoots(int n) {
    assert((n & -n) == n && ((P - 1) & (n - 1)) == 0);
    int lg = std::__lg(std::max(n, 4)) - 1;
    if (int(roots.size()) >= 1 << lg) return;
    roots.resize(1 << lg);
    roots[0] = 1, roots[1 << (lg - 1)] = power(Z(primitiveRoot), (P - 1) / (2 << lg));
    for (int i = lg - 1; i--; ) roots[1 << i] = roots[2 << i] * roots[2 << i];
    for (int i = 1; i < 1 << lg; ++i) roots[i] = roots[i & (i - 1)] * roots[i & -i];
}

void dft(Vector<Z> &a) {
    int n = int(a.size());
    assert((n & -n) == n), initRoots(n);
    for (int l = n / 2; l; l /= 2) {
        auto w = roots.begin();
        // for (int p = 0; p < n; p += 2 * l) {
        //     for (int i = p; i < p + l; ++i) {
        //         Z x = *w * a[i + l];
        //         a[i + l] = a[i] - x, a[i] = a[i] + x;
        //     }
        //     ++w;
        // }
        for (auto p = a.begin(); p != a.end(); p += 2 * l) {
            for (auto i = p; i != p + l; ++i) {
                Z x = *w * *(i + l);
                *(i + l) = *i - x, *i = *i + x;
            }
            ++w;
        }
    }
}
void idft(Vector<Z> &a) {
    int n = int(a.size());
    assert((n & -n) == n), initRoots(n);
    for (int l = 1; l < n; l *= 2) {
        auto w = roots.begin();
        for (int p = 0; p < n; p += 2 * l) {
            for (int i = p; i < p + l; ++i) {
                Z x = a[i] + a[i + l];
                a[i + l] = *w * (a[i] - a[i + l]), a[i] = x;
            }
            ++w;
        }
    }
    std::reverse(std::next(a.begin()), a.end());
    Z c = (1 - P) / n;
    for (auto &x : a) x *= c;
}
struct Poly : public Vector<Z> {
    Poly() = default;
    explicit Poly(int n) : Vector<Z>(n) {}
    explicit Poly(const Vector<Z> &a) : Vector<Z>{a} {}
    Poly(std::initializer_list<Z> a) : Vector<Z>{a} {}
    template <typename InputIt, typename = std::_RequireInputIter<InputIt>>
    explicit Poly(InputIt first, InputIt last) : Vector<Z>(first, last) {}
    template <typename F> explicit Poly(int n, F &&f) : Poly(n) {
        std::generate(begin(), end(), [&, i = 0]() mutable { return f(i++); });
    }

    Poly shift(int k) const {
        if (k >= 0) {
            auto f = *this; f.insert(f.begin(), k, 0);
            return f;
        } else if (int(size()) <= -k) {
            return Poly{};
        } else {
            return Poly(begin() + -k, end());
        }
    }
    Poly trunc(int k) const { auto f = *this; f.resize(k); return f; }
    Z get(int p) const {
        if (p < 0 || int(size()) <= p) return 0;
        return operator[](p);
    }

    friend Poly operator+(const Poly &a, const Poly &b) {
        Poly c(std::max(a.size(), b.size()));
        for (int i = 0; i < int(c.size()); ++i) c[i] = a.get(i) + b.get(i);
        return c;
    }
    friend Poly operator-(const Poly &a, const Poly &b) {
        Poly c(std::max(a.size(), b.size()));
        for (int i = 0; i < int(c.size()); ++i) c[i] = a.get(i) - b.get(i);
        return c;
    }
    friend Poly operator-(const Poly &a) {
        Poly c(a.size());
        for (int i = 0; i < int(a.size()); ++i) c[i] = -a[i];
        return c;
    }
    friend Poly operator*(Poly a, Poly b) {
        if (a.empty() || b.empty()) return Poly{};
        if (a.size() < b.size()) std::swap(a, b);
        int n = 1, m = int(a.size()) + int(b.size()) - 1;
        // if (int(b.size()) < 128) {
        //     Poly c(m);
        //     for (int i = 0; i < int(a.size()); ++i) for (int j = 0; j < int(b.size()); ++j)
        //         c[i + j] += a[i] * b[j];
        //     return c;
        // }
        while (n < m) n *= 2;
        assert(((P - 1) & (n - 1)) == 0);
        Clock clock{"Poly"};
        initRoots(n);
        clock.step("Init Roots");
        a.resize(n), dft(a);
        clock.step("Dft A");
        b.resize(n), dft(b);
        clock.step("Dft B");
        for (int i = 0; i < n; ++i) a[i] *= b[i];
        clock.step("Dot");
        idft(a), a.resize(m);
        clock.step("Idft");
        return a;
    }
    friend Poly operator*(Poly a, Z b) {
        for (int i = 0; i < int(a.size()); ++i) a[i] *= b;
        return a;
    }
    friend Poly operator*(Z a, const Poly &b) { return b * a; }
    friend Poly operator/(Poly a, Z b) {
        for (int i = 0; i < int(a.size()); ++i) a[i] /= b;
        return a;
    }
    Poly &operator+=(const Poly &b) { return *this = *this + b; }
    Poly &operator-=(const Poly &b) { return *this = *this - b; }
    Poly &operator*=(const Poly &b) { return *this = *this * b; }
    Poly &operator*=(Z b) { return *this = *this * b; }
    Poly &operator/=(Z b) { return *this = *this / b; }
};
}

using Polynomial::Poly;

inline char read_char() {
    constexpr int BufSize = 1 << 20;
    static char buf[BufSize], *p1, *p2;
    static std::streambuf *inbuf = std::cin.rdbuf();
    return p1 == p2 && (p2 = (p1 = buf) + inbuf->sgetn(buf, BufSize), p1 == p2) ? EOF : *p1++;
}
template <typename T> void read(T &x) {
    x = 0; char c = read_char(); bool f = false;
    while (!isdigit(c)) f |= (c == '-'), c = read_char();
    while (isdigit(c)) x = x * 10 + c - '0', c = read_char();
    if (f) x *= -1;
}
template <> void read(Z &x) { read(x.x), assert(0 <= x.x && x.x < P); }
inline void print_char(char c) {
    static std::streambuf *outbuf = std::cout.rdbuf();
    outbuf->sputc(c);
}
template <typename T> void print(T x) {
    if (x < 0) print_char('-'), x = -x;
    static char stk[50]; int top = 0;
    do stk[top++] = x % 10 + '0', x /= 10; while (x > 0);
    while (top--) print_char(stk[top]);
}
template <> void print(Z x) { print(x.val()); }

int main() {
#ifndef ONLINE_JUDGE
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
#endif
    std::cin.tie(nullptr)->sync_with_stdio(false);

    auto readPoly = [&](int n) {
        Poly f(n); for (auto &x : f) read(x);
        return f;
    };
    int n, m; read(n), read(m), ++n, ++m;
    auto f = readPoly(n), g = readPoly(m);

    f *= g;

    for (auto x : f) print(x), print_char(' ');

    return 0;
}
/*
init: 0.009s
FFT #1: 0.030s
FFT #2: 0.031s
mul: 0.003s
IFFT #1: 0.044s
*/

评测结果