Language: C++


using namespace std;

//#define fileio

#ifndef fileio
#include <iostream>
#endif
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <assert.h>
#include <functional>
#include <math.h>
#include <string>
#include <ctime>
#include <intrin.h>


typedef long long ll;

#ifdef fileio
ifstream cin;
ofstream cout;
#endif


template< int mod >
struct ModInt {
    int x;

    ModInt() : x(0) {}

    ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}

    ModInt& operator+=(const ModInt& p) {
        if ((x += p.x) >= mod) x -= mod;
        return *this;
    }

    ModInt& operator-=(const ModInt& p) {
        if ((x += mod - p.x) >= mod) x -= mod;
        return *this;
    }

    ModInt& operator*=(const ModInt& p) {
        x = (int)(1LL * x * p.x % mod);
        return *this;
    }

    ModInt& operator/=(const ModInt& p) {
        *this *= p.inverse();
        return *this;
    }

    ModInt operator-() const { return ModInt(-x); }

    ModInt operator+(const ModInt& p) const { return ModInt(*this) += p; }

    ModInt operator-(const ModInt& p) const { return ModInt(*this) -= p; }

    ModInt operator*(const ModInt& p) const { return ModInt(*this) *= p; }

    ModInt operator/(const ModInt& p) const { return ModInt(*this) /= p; }

    bool operator==(const ModInt& p) const { return x == p.x; }

    bool operator!=(const ModInt& p) const { return x != p.x; }

    ModInt inverse() const {
        int a = x, b = mod, u = 1, v = 0, t;
        while (b > 0) {
            t = a / b;
            swap(a -= t * b, b);
            swap(u -= t * v, v);
        }
        return ModInt(u);
    }

    ModInt pow(int64_t n) const {
        ModInt ret(1), mul(x);
        while (n > 0) {
            if (n & 1) ret *= mul;
            mul *= mul;
            n >>= 1;
        }
        return ret;
    }

    friend ostream& operator<<(ostream& os, const ModInt& p) {
        return os << p.x;
    }

    friend istream& operator>>(istream& is, ModInt& a) {
        int64_t t;
        is >> t;
        a = ModInt< mod >(t);
        return (is);
    }

    static int get_mod() { return mod; }
};

using mint = ModInt< 998244353 >;

static uint32_t __inline ctz(uint32_t x)
{
    unsigned long r = 0;
    _BitScanForward(&r, x);
    return r;
}

template< typename Mint >
struct NTT {

    vector< Mint > dw, idw;
    int max_base;
    Mint root;

    NTT() {
        const unsigned mod = Mint::get_mod();
        assert(mod >= 3 && mod % 2 == 1);
        auto tmp = mod - 1;
        max_base = 0;
        while (tmp % 2 == 0) tmp >>= 1, max_base++;
        root = 2;
        while (root.pow((mod - 1) >> 1) == 1) root += 1;
        assert(root.pow(mod - 1) == 1);
        dw.resize(max_base);
        idw.resize(max_base);
        for (int i = 0; i < max_base; i++) {
            dw[i] = -root.pow((mod - 1) >> (i + 2));
            idw[i] = Mint(1) / dw[i];
        }
    }

    void ntt(vector< Mint >& a) {
        const int n = (int)a.size();
        assert((n & (n - 1)) == 0);
        assert(ctz(n) <= max_base);
        for (int m = n; m >>= 1;) {
            Mint w = 1;
            for (int s = 0, k = 0; s < n; s += 2 * m) {
                for (int i = s, j = s + m; i < s + m; ++i, ++j) {
                    auto x = a[i], y = a[j] * w;
                    a[i] = x + y, a[j] = x - y;
                }
                w *= dw[ctz(++k)];
            }
        }
    }

    void intt(vector< Mint >& a, bool f = true) {
        const int n = (int)a.size();
        assert((n & (n - 1)) == 0);
        assert(ctz(n) <= max_base);
        for (int m = 1; m < n; m *= 2) {
            Mint w = 1;
            for (int s = 0, k = 0; s < n; s += 2 * m) {
                for (int i = s, j = s + m; i < s + m; ++i, ++j) {
                    auto x = a[i], y = a[j];
                    a[i] = x + y, a[j] = (x - y) * w;
                }
                w *= idw[ctz(++k)];
            }
        }
        if (f) {
            Mint inv_sz = Mint(1) / n;
            for (int i = 0; i < n; i++) a[i] *= inv_sz;
        }
    }

    vector< Mint > multiply(vector< Mint > a, vector< Mint > b) {
        //reverse(a.begin(), a.end());
        //reverse(b.begin(), b.end());
        int need = a.size() + b.size() - 1;
        int nbase = 1;
        while ((1 << nbase) < need) nbase++;
        int sz = 1 << nbase;
        a.resize(sz, 0);
        b.resize(sz, 0);
        ntt(a);
        ntt(b);
        Mint inv_sz = Mint(1) / sz;
        for (int i = 0; i < sz; i++) a[i] *= b[i] * inv_sz;
        intt(a, false);
        a.resize(need);
        //reverse(a.begin(), a.end());
        return a;
    }
};

NTT<mint> ntt;


int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifdef fileio
    cin.open("Text.txt");
    cout.open("Output.txt");
#endif

    int n;
    int m;
    cin >> n >> m;

    vector<mint> a;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        a.push_back(x);
    }

    vector<mint> b;
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        b.push_back(x);
    }

    vector<mint> c = ntt.multiply(a, b);


    for (int i = 0; i < c.size(); i++) {
        cout << c[i] << " ";
    }
    cout << endl;



}


Compiler output:
a.cc:20:10: fatal error: intrin.h: No such file or directory
   20 | #include <intrin.h>
      |          ^~~~~~~~~~
compilation terminated.