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>


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:108:8: error: 'uint32_t' does not name a type
  108 | static uint32_t __inline ctz(uint32_t x)
      |        ^~~~~~~~
a.cc:20:1: note: 'uint32_t' is defined in header '<cstdint>'; this is probably fixable by adding '#include <cstdint>'
   19 | #include <ctime>
  +++ |+#include <cstdint>
   20 | 
In file included from a.cc:15:
a.cc: In member function 'void NTT<Mint>::ntt(std::vector<_Tp>&)':
a.cc:142:16: error: there are no arguments to 'ctz' that depend on a template parameter, so a declaration of 'ctz' must be available [-fpermissive]
  142 |         assert(ctz(n) <= max_base);
      |                ^~~
a.cc:142:16: note: (if you use '-fpermissive', G++ will accept your code, but allowing the use of an undeclared name is deprecated)
a.cc:150:25: error: there are no arguments to 'ctz' that depend on a template parameter, so a declaration of 'ctz' must be available [-fpermissive]
  150 |                 w *= dw[ctz(++k)];
      |                         ^~~
a.cc: In member function 'void NTT<Mint>::intt(std::vector<_Tp>&, bool)':
a.cc:158:16: error: there are no arguments to 'ctz' that depend on a template parameter, so a declaration of 'ctz' must be available [-fpermissive]
  158 |         assert(ctz(n) <= max_base);
      |                ^~~
a.cc:166:26: error: there are no arguments to 'ctz' that depend on a template parameter, so a declaration of 'ctz' must be available [-fpermissive]
  166 |                 w *= idw[ctz(++k)];
      |                          ^~~
a.cc: In instantiation of 'void NTT<Mint>::ntt(std::vector<_Tp>&) [with Mint = ModInt<998244353>]':
a.cc:184:9:   required from 'std::vector<_Tp> NTT<Mint>::multiply(std::vector<_Tp>, std::vector<_Tp>) [with Mint = ModInt<998244353>]'
  184 |         ntt(a);
      |         ^~~
a.cc:223:34:   required from here
  223 |     vector<mint> c = ntt.multiply(a, b);
      |                      ~~~~~~~~~~~~^~~~~~
a.cc:142:19: error: 'ctz' was not declared in this scope
  142 |         assert(ctz(n) <= max_base);
      |                ~~~^~~
a.cc:150:28: error: 'ctz' was not declared in this scope, and no declarations were found by argument-dependent lookup at the point of instantiation
  150 |                 w *= dw[ctz(++k)];
      |                         ~~~^~~~~
a.cc:142:19: note: 'ctz' declared here, later in the translation unit
  142 |         assert(ctz(n) <= max_base);
      |                ~~~^~~
a.cc: In instantiation of 'void NTT<Mint>::intt(std::vector<_Tp>&, bool) [with Mint = ModInt<998244353>]':
a.cc:188:9:   required from 'std::vector<_Tp> NTT<Mint>::multiply(std::vector<_Tp>, std::vector<_Tp>) [with Mint = ModInt<998244353>]'
  188 |         intt(a, false);
      |         ^~~~
a.cc:223:34:   required from here
  223 |     vector<mint> c = ntt.multiply(a, b);
      |                      ~~~~~~~~~~~~^~~~~~
a.cc:158:19: error: 'ctz' was not declared in this scope
  158 |         assert(ctz(n) <= max_base);
      |                ~~~^~~
a.cc:166:29: error: 'ctz' was not declared in this scope, and no declarations were found by argument-dependent lookup at the point of instantiation
  166 |                 w *= idw[ctz(++k)];
      |                          ~~~^~~~~
a.cc:158:19: note: 'ctz' declared here, later in the translation unit
  158 |         assert(ctz(n) <= max_base);
      |                ~~~^~~