代码

/* 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() << "s\n";
        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);
    if (int(roots.size()) >= n) return;
    roots.resize(n);
    for (int l = 1; l < n; l *= 2) {
        auto w = roots.begin() + l; w[0] = 1;
        Z x = power(Z(primitiveRoot), (P - 1) / l / 2);
        for (int i = 1; i < l; ++i) w[i] = w[i - 1] * x;
    }
}

inline void applyDft(int &x, int &y, int w) {
    int t = x - y;
    x = x + y; if (x >= P) x -= P;
    y = 1ll * t * w % P; if (y < 0) y += P;
}
inline void applyIdft(int &x, int &y, int w) {
    int t = 1ll * y * w % P;
    y = x - t; if (y < 0) y += P;
    x = x + t; if (x >= P) x -= P;
}

void dft(Vector<Z> &a) {
    int n = int(a.size());
    assert((n & -n) == n), initRoots(n);
    for (int l = n / 2; l; l /= 2)
        for (auto p = a.begin(); p != a.end(); p += 2 * l)
            for (auto i = p, w = roots.begin() + l; i != p + l; ++i, ++w)
                applyDft(i->x, (i + l)->x, w->x);
}
void idft(Vector<Z> &a) {
    int n = int(a.size());
    assert((n & -n) == n), initRoots(n);
    for (int l = 1; l < n; l *= 2)
        for (auto p = a.begin(); p != a.end(); p += 2 * l)
            for (auto i = p, w = roots.begin() + l; i != p + l; ++i, ++w)
                applyIdft(i->x, (i + l)->x, w->x);
    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), b.resize(n);
        clock.step("Resize");
        dft(a);
        clock.step("Dft A");
        dft(b);
        clock.step("Dft B");
        Z c = (1 - P) / n;
        for (int i = 0; i < n; ++i) a[i] *= b[i] * c;
        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()); }

#ifdef TEST
int main() {
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
    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;
}
#else
void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c) {
    ++n, ++m;
    Poly f(n), g(m);
    auto p = (Z *)a, q = (Z *)b, r = (Z *)c;
    std::copy(p, p + n, f.begin()), std::copy(q, q + m, g.begin());
    f *= g;
    std::copy(f.begin(), f.begin() + n + m - 1, r);
}
#endif

/*
Poly(Init Roots): 0.009526s
Poly(Resize): 0.006484s
Poly(Dft A): 0.035665s
Poly(Dft B): 0.032839s
Poly(Dot): 0.002862s
Poly(Idft): 0.04848s

Poly(Init Roots): 0.010501s
Poly(Resize): 0.006465s
Poly(Dft A): 0.035205s
Poly(Dft B): 0.034035s
Poly(Dot): 0.002189s
Poly(Idft): 0.057046s

Poly(Init Roots): 0.003202s
Poly(Resize): 0.009285s
Poly(Dft A): 0.056008s
Poly(Dft B): 0.048367s
Poly(Dot): 0.003277s
Poly(Idft): 0.038788s

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

评测结果