Submit Info #55971

Problem Lang User Status Time Memory
Multipoint Evaluation cpp pikelrik AC 2176 ms 45.67 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.72 MiB
example_01 AC 1 ms 0.61 MiB
max_random_00 AC 2176 ms 45.67 MiB
max_random_01 AC 2172 ms 45.67 MiB
random_00 AC 311 ms 14.02 MiB
random_01 AC 269 ms 9.79 MiB
random_02 AC 1074 ms 30.97 MiB

#include <bits/stdc++.h> using namespace std; template<int M> struct static_mint { static_assert(0 < M, "Module must be positive"); int val; static_mint() : val() {} static_mint(long long x) : val(x % M) { if (val < 0) val += M; } static_mint pow(long long n) const { static_mint ans = 1, x(*this); for (; n > 0; n /= 2) { if (n & 1) ans *= x; x *= x; } return ans; } static_mint inv() const { return pow(M - 2); } static_mint operator+() const { static_mint m; m.val = val; return m; } static_mint operator-() const { static_mint m; m.val = (val == 0 ? 0 : M - val); return m; } static_mint &operator+=(const static_mint &m) { if ((val += m.val) >= M) val -= M; return *this; } static_mint &operator-=(const static_mint &m) { if ((val -= m.val) < 0) val += M; return *this; } static_mint &operator*=(const static_mint &m) { val = (long long) val * m.val % M; return *this; } static_mint &operator/=(const static_mint &m) { val = (long long) val * m.inv().val % M; return *this; } friend static_mint operator+(const static_mint &lhs, const static_mint &rhs) { return static_mint(lhs) += rhs; } friend static_mint operator-(const static_mint &lhs, const static_mint &rhs) { return static_mint(lhs) -= rhs; } friend static_mint operator*(const static_mint &lhs, const static_mint &rhs) { return static_mint(lhs) *= rhs; } friend static_mint operator/(const static_mint &lhs, const static_mint &rhs) { return static_mint(lhs) /= rhs; } friend bool operator==(const static_mint &lhs, const static_mint &rhs) { return lhs.val == rhs.val; } friend bool operator!=(const static_mint &lhs, const static_mint &rhs) { return lhs.val != rhs.val; } static_mint &operator++() { return *this += 1; } static_mint &operator--() { return *this -= 1; } static_mint operator++(int) { static_mint result(*this); *this += 1; return result; } static_mint operator--(int) { static_mint result(*this); *this -= 1; return result; } template<typename T> explicit operator T() const { return T(val); } friend std::ostream &operator<<(std::ostream &os, const static_mint &m) { return os << m.val; } friend std::istream &operator>>(std::istream &is, static_mint &m) { long long x; return is >> x, m = x, is; } }; template <typename> struct is_mint_helper : std::false_type { }; template <int M> struct is_mint_helper<static_mint<M>> : std::true_type { }; template <typename T> struct is_mint : is_mint_helper<typename std::decay<T>::type> { }; namespace ntt { template<int P> struct prime_info { constexpr static int root = 0, root_pw = 0; }; template<> struct prime_info<7340033> { constexpr static int root = 5, root_pw = 1 << 20; }; template<> struct prime_info<998244353> { constexpr static int root = 15311432, root_pw = 1 << 23; }; template<> struct prime_info<754974721> { constexpr static int root = 739831874, root_pw = 1 << 24; }; template<> struct prime_info<167772161> { constexpr static int root = 243, root_pw = 1 << 25; }; template<> struct prime_info<469762049> { constexpr static int root = 2187, root_pw = 1 << 26; }; std::vector<int> rev = {0}; void compute_bit_reverse(int lg) { static int computed = 0; if (lg <= computed) return; rev.resize(1 << lg); for (int i = (1 << computed); i < (1 << lg); i++) { rev[i] = (rev[i >> 1] >> 1) ^ ((i & 1) << 30); } computed = lg; } template<int M> std::vector<static_mint<M>> root = {0, 1}; template<int M> void compute_roots(int lg) { static int computed = 1; if (lg <= computed) return; root<M>.resize(1 << lg); for (int k = computed; k < lg; k++) { static_mint<M> z(prime_info<M>::root); for (int i = (1 << (k + 1)); i < prime_info<M>::root_pw; i <<= 1) { z *= z; } for (int i = (1 << (k - 1)); i < (1 << k); i++) { root<M>[i << 1] = root<M>[i]; root<M>[i << 1 | 1] = root<M>[i] * z; } } } template<int M> void ntt(std::vector<static_mint<M>> &a) { int n = int(a.size()), lg = 32 - __builtin_clz(n) - 1; compute_bit_reverse(lg); compute_roots<M>(lg); int shift = 31 - lg; for (int i = 0; i < n; i++) { if (i < (rev[i] >> shift)) { std::swap(a[i], a[rev[i] >> shift]); } } for (int k = 1; k < n; k <<= 1) { static_mint<M> wl = prime_info<M>::root; for (int i = 2 * k; i < prime_info<M>::root_pw; i <<= 1) { wl *= wl; } for (int i = 0; i < n; i += 2 * k) { for (int j = 0; j < k; j++) { static_mint<M> z = root<M>[j + k] * a[i + j + k]; a[i + j + k] = a[i + j] - z; a[i + j] = a[i + j] + z; } } } } template<int M> std::enable_if_t<prime_info<M>::root != 0, std::vector<static_mint<M>>> convolution(std::vector<static_mint<M>> a, std::vector<static_mint<M>> b) { int n = 1; while (n < a.size() + b.size()) { n <<= 1; } a.resize(n); b.resize(n); ntt(a), ntt(b); static_mint<M> n_inv = static_mint<M>(n).inv(); for (int i = 0; i < n; i++) { a[i] *= b[i] * n_inv; } reverse(a.begin() + 1, a.end()); ntt(a); return a; } template<int M> static_mint<M> garner(int a1, int a2, int a3) { constexpr static int M1 = 754974721, M2 = 167772161, M3 = 469762049; const static int R12 = static_mint<M2>(M1).inv().val; const static int R13 = static_mint<M3>(M1).inv().val; const static int R23 = static_mint<M3>(M2).inv().val; int x1 = a1; int x2 = (long long) (a2 - x1) * R12 % M2; if (x2 < 0) x2 += M2; int x3 = ((long long) (a3 - x1) * R13 % M3 - x2) * R23 % M3; if (x3 < 0) x3 += M3; return static_mint<M>(x1) + static_mint<M>(x2) * M1 + static_mint<M>(x3) * M1 * M2; } template<int M> std::enable_if_t<prime_info<M>::root == 0, std::vector<static_mint<M>>> convolution(std::vector<static_mint<M>> a, const std::vector<static_mint<M>> &b) { constexpr static int M1 = 754974721, M2 = 167772161, M3 = 469762049; auto c1 = convolution(vector<static_mint<M1>>(a.begin(), a.end()), vector<static_mint<M1>>(b.begin(), b.end())); auto c2 = convolution(vector<static_mint<M2>>(a.begin(), a.end()), vector<static_mint<M2>>(b.begin(), b.end())); auto c3 = convolution(vector<static_mint<M3>>(a.begin(), a.end()), vector<static_mint<M3>>(b.begin(), b.end())); int n = int(c1.size()); a.resize(n); for (int i = 0; i < n; i++) { a[i] = garner<M>(c1[i].val, c2[i].val, c3[i].val); } return a; } template<int M = 998244353, typename T> std::enable_if_t<!is_mint<T>::value, std::vector<T>> convolution(const std::vector<T> &a, const std::vector<T> &b) { auto f = convolution(std::vector<static_mint<M>>(a.begin(), a.end()), std::vector<static_mint<M>>(b.begin(), b.end())); return vector<T>(f.begin(), f.end()); } template<typename T> void normalize(const std::vector<T> &a) { for (int i = int(a.size()) - 1; i >= 0; i--) { if (a[i]) { a.resize(i + 1); return; } } a.clear(); } } template <typename T> struct polynomial : public std::vector<T> { template <typename...args> polynomial(args...A) : std::vector<T>(A...) { } polynomial(const std::initializer_list<T> &l) : std::vector<T>(l) { } int deg() const noexcept { return (int) this->size() - 1; } void normalize() { for (int i = deg(); i >= 0; i--) { if ((*this)[i]) { this->resize(i + 1); return; } } this->clear(); } polynomial &operator+=(const polynomial &q) { if (q.size() > this->size()) { this->resize(q.size()); } for (int i = 0; i < q.size(); i++) { (*this)[i] += q[i]; } normalize(); return *this; } polynomial &operator-=(const polynomial &q) { if (q.size() > this->size()) { this->resize(q.size()); } for (int i = 0; i < q.size(); i++) { (*this)[i] -= q[i]; } normalize(); return *this; } void naive_mul(polynomial &a, const polynomial &b) const { polynomial result(a.deg() + b.deg() + 1); for (int i = 0; i <= a.deg(); i++) { for (int j = 0; j <= b.deg(); j++) { result[i + j] += a[i] * b[j]; } } a.swap(result); } void ntt_mul(polynomial &fa, polynomial fb) const { fa = ntt::convolution(fa, fb); } polynomial &operator*=(const polynomial &q) { if (this->empty() || q.empty()) { this->clear(); } else if (this->size() <= 60) { naive_mul(*this, q); } else { ntt_mul(*this, q); } normalize(); return *this; } polynomial &operator*=(const T &val) { for (auto &x : *this) { x *= val; } return *this; } void divide(polynomial &a, polynomial b) const { assert(!b.empty()); if (a.deg() < b.deg()) { a.clear(); return; } reverse(a.begin(), a.end()); int sz = a.deg() - b.deg() + 1; a %= sz; reverse(b.begin(), b.end()); a *= b.inv(sz); a %= sz; reverse(a.begin(), a.end()); } polynomial &operator/=(const polynomial &q) { divide(*this, q); normalize(); return *this; } polynomial &operator/=(T val) { val = 1 / val; for (auto &x : *this) { x *= val; } return *this; } polynomial &operator%=(const polynomial &q) { *this -= q * (*this / q); normalize(); return *this; } polynomial &operator%=(size_t k) { if (k <= deg()) this->resize(k); return *this; } polynomial &operator<<=(size_t k) { if (this->size() <= k) { this->clear(); } else { polynomial result(this->begin() + k, this->end()); this->swap(result); } return *this; } polynomial &operator>>=(size_t k) { polynomial result(this->size() + k); std::copy(this->begin(), this->end(), result.begin() + k); this->swap(result); return *this; } T operator()(const T &val) { T ans = 0; for (int i = deg(); i >= 0; i--) { ans = (ans * val + (*this)[i]); } return ans; } friend polynomial operator+(polynomial p, const polynomial &q) { p += q; return p; } friend polynomial operator-(polynomial p, const polynomial &q) { p -= q; return p; } friend polynomial operator*(polynomial p, const polynomial &q) { p *= q; return p; } friend polynomial operator*(polynomial p, const T &val) { p *= val; return p; } friend polynomial operator*(const T &val, polynomial p) { p *= val; return p; } friend polynomial operator/(polynomial p, const polynomial &q) { p /= q; return p; } friend polynomial operator/(polynomial p, const T &val) { p /= val; return p; } friend polynomial operator%(polynomial p, const polynomial &q) { p %= q; return p; } friend polynomial operator%(polynomial p, size_t k) { p %= k; return p; } friend polynomial operator<<(polynomial p, size_t k) { p <<= k; return p; } friend polynomial operator>>(polynomial p, size_t k) { p >>= k; return p; } polynomial inv(int k = -1) const { if (k == -1) k = this->size(); assert(!this->empty() && (*this)[0] != 0); polynomial b(1, 1 / (*this)[0]); for (int i = 2; i <= (k << 1); i <<= 1) { polynomial temp = (*this) % i; temp *= b, temp %= i; temp *= T(-1), temp[0] += 2; b *= temp, b %= i; } b.resize(k); return b; } polynomial derivative() const { if (deg() < 1) { return {}; } polynomial result(this->size() - 1); for (int i = 1; i < this->size(); i++) { result[i - 1] = i * (*this)[i]; } return result; } polynomial integral() const { if (this->empty()) { return {}; } polynomial result(this->size() + 1); for (int i = 0; i < this->size(); i++) { result[i + 1] = (*this)[i] / (i + 1); } return result; } polynomial log(int k = -1) const { assert(!this->empty() && (*this)[0] == 1); if (k == -1) k = this->size(); polynomial result = ((derivative() % k) * inv(k)).integral(); result.resize(k); return result; } polynomial exp(int k = -1) const { assert(this->empty() || (*this)[0] == 0); if (k == -1) k = this->size(); polynomial q(1, 1); for (int i = 2; i <= (k << 1); i <<= 1) { polynomial temp = polynomial(1, 1) + (*this % i) - q.log(i); q *= temp, q %= i; } q.resize(k); return q; } polynomial pow(int n, int k = -1) const { if (k == -1) k = this->size(); if (this->empty()) return polynomial(k); T alpha = 0; int pw = 0; for (int i = 0; i < this->size(); i++) { if ((*this)[i]) { alpha = (*this)[i]; pw = i; break; } } if ((long long)pw * n >= k) { return polynomial(k); } polynomial<T> b = (*this) << pw; b /= alpha; b = (T(n) * b.log(k)).exp(k); b >>= pw * n; b *= alpha.pow(n); b.resize(k); return b; } template <typename U> std::vector<T> multipoint_evaluation(const std::vector<U> &pt) { int n = (int) pt.size(); std::vector<polynomial> tree(4 * n); auto build = [&](int i, int l, int r, const auto &self) -> void { if (l == r) { tree[i] = {T(-pt[l]), 1}; } else { int mid = (l + r) >> 1; self(i << 1, l, mid, self); self(i << 1 | 1, mid + 1, r, self); tree[i] = tree[i << 1] * tree[i << 1 | 1]; } }; build(1, 0, n - 1, build); std::vector<T> result(n); auto dfs = [&](int i, int l, int r, polynomial p, const auto &self) -> void { p %= tree[i]; if (l == r) { result[l] = (p.empty() ? 0 : p[0]); } else { int mid = (l + r) >> 1; self(i << 1, l, mid, p, self); self(i << 1 | 1, mid + 1, r, p, self); } }; dfs(1, 0, n - 1, *this, dfs); return result; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); using mint = static_mint<998244353>; int n, m; cin >> n >> m; polynomial<mint> c(n), p(m); for (int i = 0; i < n; i++) cin >> c[i]; for (int i = 0; i < m; i++) cin >> p[i]; auto result = c.multipoint_evaluation(p); for (int i = 0; i < m; i++) { cout << result[i] << ' '; } cout << '\n'; return 0; }