Submission #10030228

---

Source Code Expand

#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#include <bits/stdc++.h>

template <int MODULUS = 1000000007>
struct modulo_int {
private:

    long long value;
    constexpr void normalize() {
        value %= MODULUS;
        if (value < 0) value += MODULUS;
    }

public:

    constexpr modulo_int(const long long& value_ = 0) : value(value_) { normalize(); }
    constexpr modulo_int operator - () const { return modulo_int(MODULUS - value); }
    constexpr modulo_int operator ~ () const { return power(MODULUS - 2); }
    constexpr long long operator () () const { return value; }

    constexpr modulo_int operator + (const modulo_int& rhs) const { return modulo_int(*this) += rhs; }
    constexpr modulo_int& operator += (const modulo_int& rhs) {
        if ((value += rhs.value) >= MODULUS) value -= MODULUS;
        return (*this);
    }

    constexpr modulo_int operator - (const modulo_int& rhs) const { return modulo_int(*this) -= rhs; }
    constexpr modulo_int& operator -= (const modulo_int& rhs) {
        if ((value += MODULUS - rhs.value) >= MODULUS) value -= MODULUS;
        return (*this);
    }

    constexpr modulo_int operator * (const modulo_int& rhs) const { return modulo_int(*this) *= rhs; }
    constexpr modulo_int& operator *= (const modulo_int& rhs) {
        (value *= rhs.value) %= MODULUS;
        return (*this);
    }

    constexpr modulo_int operator / (const modulo_int& rhs) const { return modulo_int(*this) /= rhs; }
    constexpr modulo_int& operator /= (const modulo_int& rhs) {
        return (*this) *= ~rhs;
    }

    constexpr modulo_int power(const long long& power_) const {
        modulo_int result(1), mult(*this);
        for (long long t = power_; t > 0; t >>= 1) {
            if (t & 1) result *= mult;
            mult *= mult;
        }
        return result;
    }

    friend std::istream& operator >> (std::istream& stream, modulo_int& lhs) {
        stream >> lhs.value;
        lhs.normalize();
        return stream;
    }

    friend std::ostream& operator << (std::ostream& stream, const modulo_int& rhs) {
        return stream << rhs.value;
    }

};

template <class T, int MODULUS = 998244353, int PRIM = 3>
void modulo_transform(std::vector<modulo_int<MODULUS>>& F, const bool& inverse = false) {
    int F_sz = F.size();
    for (int i = 0, j = 1; j < F_sz - 1; ++j) {
        for (int k = (F_sz >> 1); k > (i ^= k); k >>= 1);
        if (i < j) std::swap(F[i], F[j]);
    }
    modulo_int<MODULUS> zeta = modulo_int<MODULUS>(PRIM).power((MODULUS - 1) / F_sz);
    if (inverse) zeta = ~zeta;
    std::vector<modulo_int<MODULUS>> coeff(F_sz);
    coeff[0] = 1;
    for (int i = 1; i < F_sz; ++i) {
        coeff[i] = coeff[i - 1] * zeta;
    }
    int index;
    modulo_int<MODULUS> first, second;
    for (int len = 1, bit = (F_sz >> 1); len < F_sz; len <<= 1, bit >>= 1) {
        for (int k = 0; k < F_sz; k += (len << 1)) {
            index = 0;
            for (int i = 0; i < len; ++i) {
                first = F[i + k];
                second = F[(i + k) ^ len];
                F[i + k] = coeff[0] * first + coeff[index] * second;
                F[(i + k) ^ len] = coeff[0] * first + coeff[index + (F_sz >> 1)] * second;
                index += bit;
            }
        }
    }
}

template <class T, int MODULUS = 998244353, int PRIM = 3>
std::vector<T> convolute(const std::vector<T>& A, const std::vector<T>& B) {
    int A_sz = A.size(), B_sz = B.size(), result_sz = A_sz + B_sz - 1;
    int X_sz = 1;
    while (X_sz < result_sz) {
        X_sz <<= 1;
    }
    std::vector<modulo_int<MODULUS>> C(X_sz), D(X_sz);
    for (int i = 0; i < A_sz; ++i) {
        C[i] = A[i];
    }
    for (int i = 0; i < B_sz; ++i) {
        D[i] = B[i];
    }
    modulo_transform<T, MODULUS, PRIM>(C);
    modulo_transform<T, MODULUS, PRIM>(D);
    for (int i = 0; i < X_sz; ++i) {
        C[i] *= D[i];    
    }
    modulo_transform<T, MODULUS, PRIM>(C, true);
    modulo_int<MODULUS> sz_inv = ~modulo_int<MODULUS>(X_sz);
    std::vector<T> result(result_sz);
    for (int i = 0; i < result_sz; ++i) {
        result[i] = static_cast<T>((C[i] * sz_inv)());
    }
    return result;
}

inline void rd(int &x) {
  int c;
  while ((c = getchar_unlocked() - '0') >= 0) {
    x = x * 10 + c;
  }
}
 
char out[15];
inline void pt(int x) {
  int d = 0;
  if (x == 0) {
    out[d] = '0';
    ++d;
  }
  for (; x > 0; ++d) {
    out[d] = (x % 10) + '0';
    x /= 10;
  }
  while (d--) {
    putchar_unlocked(out[d]);
  }
  putchar_unlocked('\n');
}

int main() {
  int N;
  rd(N);
  std::vector<int> A(N), B(N);
  for (int i = 0; i < N; ++i) {
    rd(A[i]); rd(B[i]);
  }
  std::vector<int> answer = convolute<int, 998244353, 3>(A, B);
  pt(0);
  for (int i = 0; i < N + N - 1; ++i) {
    pt(answer[i]);
  }
}

Submission Info

Judge Result