Submit Info #55403

Problem Lang User Status Time Memory
Multipoint Evaluation cpp Golovanov399 AC 2382 ms 39.42 MiB

ケース詳細
Name Status Time Memory
example_00 AC 7 ms 2.70 MiB
example_01 AC 7 ms 2.71 MiB
max_random_00 AC 2382 ms 39.41 MiB
max_random_01 AC 2376 ms 39.42 MiB
random_00 AC 531 ms 13.73 MiB
random_01 AC 464 ms 10.99 MiB
random_02 AC 1705 ms 27.06 MiB

#include <bits/stdc++.h> #define all(x) (x).begin(), (x).end() #define make_unique(x) sort((x).begin(), (x).end()); (x).erase(unique((x).begin(), (x).end()), (x).end()) #define imie(x) #x << ": " << x using namespace std; template <typename T> istream& operator >>(istream& istr, vector<T>& vec) { for (auto& x : vec) { istr >> x; } return istr; } template <typename T, typename U> istream& operator >>(istream& istr, pair<T, U>& pr) { return istr >> pr.first >> pr.second; } template <typename T = int> T nxt(istream& istr = cin) { T x; istr >> x; return x; } template <typename T> struct TypeModular { using Type = typename decay<decltype(T::value)>::type; Type val; static constexpr Type mod() { return T::value; } TypeModular(long long _val = 0) { if (_val < 0 || (_val > 0 && _val >= mod())) { val = _val % mod(); if (val < 0) { val += mod(); } } else { val = _val; } } friend TypeModular operator -(const TypeModular& a) { return {-a.val}; } friend TypeModular operator +(const TypeModular& a, const TypeModular& b) { Type res = a.val + b.val; if (res >= mod()) { res -= mod(); } return {res}; } friend TypeModular operator -(const TypeModular& a, const TypeModular& b) { Type res = a.val - b.val; if (res < 0) { res += mod(); } return {res}; } friend TypeModular operator *(const TypeModular& a, const TypeModular& b) { return {1ll * a.val * b.val}; } friend TypeModular operator /(const TypeModular& a, const TypeModular& b) { return a * b.inv(); } TypeModular& operator +=(const TypeModular& b) { val += b.val; if (val >= mod()) { val -= mod(); } return *this; } TypeModular& operator -=(const TypeModular& b) { val -= b.val; if (val < 0) { val += mod(); } return *this; } TypeModular& operator *=(const TypeModular& b) { val = 1ll * val * b.val % mod(); return *this; } TypeModular& operator /=(const TypeModular& b) { *this *= b.inv(); return *this; } TypeModular& operator ++() { val += 1; if (val == mod()) { val = 0; } return *this; } TypeModular operator ++(int) { TypeModular tmp(*this); operator ++(); return tmp; } friend bool operator ==(const TypeModular& a, const TypeModular& b) { return a.val == b.val; } friend bool operator !=(const TypeModular& a, const TypeModular& b) { return a.val != b.val; } TypeModular pow(long long b) const { TypeModular res{1}, a{*this}; while (b) { if (b & 1ll) { res *= a; } b >>= 1; a *= a; } return res; } TypeModular inv() const { assert(val); return _inv(val, mod()); } int _inv(int a, int b) const { return a == 1 ? a : b - 1ll * _inv(b % a, a) * b / a % b; } explicit operator Type() const { return val; } explicit operator bool() const { return val; } }; template <typename T = int> struct integral_variable { static T value; }; template <typename T> T integral_variable<T>::value; void set_prime(int p) { integral_variable<int>::value = p; } template <typename T> ostream& operator <<(ostream& ostr, const TypeModular<T>& x) { return ostr << x.val; } template <typename T> istream& operator >>(istream& istr, TypeModular<T>& x) { x = nxt(istr); return istr; } template <int mod> using Modular = TypeModular<integral_constant<int, mod>>; template <typename outer_type, typename inner_type, int N> class IFFT { public: using Poly = vector<outer_type>; IFFT(): initialized_(false) {} ~IFFT() {} virtual Poly multiply(Poly a, Poly b) { if ((int)a.size() > N / 2 || (int)b.size() > N / 2) { Poly result(a.size() + b.size() - 1); const int low_len = (max(a.size(), b.size()) + 1) / 2; Poly a_low(a.begin(), min(a.begin() + low_len, a.end())); Poly a_high(min(a.begin() + low_len, a.end()), a.end()); Poly b_low(b.begin(), min(b.begin() + low_len, b.end())); Poly b_high(min(b.begin() + low_len, b.end()), b.end()); auto tmp = multiply(a_low, b_low); for (int i = 0; i < (int)tmp.size(); ++i) { result[i] += tmp[i]; if (low_len + i < (int)result.size()) { result[low_len + i] -= tmp[i]; } } tmp = multiply(a_high, b_high); for (int i = 0; i < (int)tmp.size(); ++i) { result[2 * low_len + i] += tmp[i]; if (low_len + i < (int)result.size()) { result[low_len + i] -= tmp[i]; } } for (int i = 0; i < (int)a_high.size(); ++i) { a_low[i] += a_high[i]; } for (int i = 0; i < (int)b_high.size(); ++i) { b_low[i] += b_high[i]; } tmp = multiply(a_low, b_low); for (int i = 0; i < (int)tmp.size(); ++i) { result[low_len + i] += tmp[i]; } return result; } int n = 1; while (n < (int)a.size() || n < (int)b.size()) { n *= 2; } vector<inner_type> ar(n + n), br(n + n); if constexpr (is_convertible_v<outer_type, inner_type>) { copy(all(a), ar.begin()); copy(all(b), br.begin()); } else { throw runtime_error("please, implement your own child multiply function"); } fft(ar); fft(br); for (int i = 0; i < (int)ar.size(); ++i) { ar[i] *= br[i]; } ifft(ar); Poly res((int)a.size() + (int)b.size() - 1); assert(res.size() <= ar.size()); if constexpr (is_convertible_v<inner_type, outer_type>) { copy_n(ar.begin(), res.size(), res.begin()); } else { throw runtime_error("please, implement your own child multiply function"); } return res; } virtual Poly square(const Poly& a) { int n = 1; while (n < (int)a.size()) { n *= 2; } vector<inner_type> ar(n + n); if constexpr (is_convertible_v<outer_type, inner_type>) { copy(all(a), ar.begin()); } else { throw runtime_error("please, implement your own child square function"); } fft(ar); for (int i = 0; i < (int)ar.size(); ++i) { ar[i] *= ar[i]; } ifft(ar); Poly res((int)a.size() + (int)a.size() - 1); assert(res.size() <= ar.size()); if constexpr (is_convertible_v<inner_type, outer_type>) { copy_n(ar.begin(), res.size(), res.begin()); } else { throw runtime_error("please, implement your own child square function"); } return res; } Poly inverse(const Poly& a, int prec) { assert(!a.empty()); assert(a[0] != 0); Poly b = {1 / a[0]}; for (int len = 1; len < prec; len *= 2) { auto tmp = multiply(b, b); if ((int)tmp.size() > prec) { tmp.resize(prec); } tmp = multiply(tmp, Poly{a.begin(), a.begin() + min(2 * len, (int)a.size())}); tmp.resize(2 * len); for (int i = 0; i < len; ++i) { tmp[i] = 2 * b[i] - tmp[i]; tmp[len + i] = -tmp[len + i]; } b.swap(tmp); } b.resize(prec); return b; } Poly derivative(Poly a) { if (a.empty()) { return a; } a.erase(a.begin()); for (int i = 0; i < (int)a.size(); ++i) { a[i] *= i + 1; } return a; } Poly primitive(Poly a) { a.insert(a.begin(), 0); for (int i = 1; i < (int)a.size(); ++i) { a[i] /= i; } return a; } Poly log(const Poly& a, int prec) { assert(!a.empty()); assert(a[0] == 1); auto res = primitive(multiply(derivative(a), inverse(a, prec))); res.resize(prec); return res; } Poly exp(const Poly& a, int prec) { assert(!a.empty()); assert(a[0] == 0); Poly b = {1}; for (int len = 1; len < prec; len *= 2) { auto tmp = Poly{a.begin(), a.begin() + min(2 * len, (int)a.size())}; tmp.resize(2 * len); tmp[0] += 1; auto l = log(b, 2 * len); for (int i = 0; i < 2 * len; ++i) { tmp[i] -= l[i]; } b = multiply(tmp, b); b.resize(2 * len); } b.resize(prec); return b; } pair<Poly, Poly> divmod(Poly a, Poly b) { assert(!b.empty()); assert(b.back() != 0); if (a.size() < b.size()) { return {{0}, a}; } reverse(all(a)); reverse(all(b)); auto q = inverse(b, a.size() - b.size() + 1); q = multiply(a, q); q.resize(a.size() - b.size() + 1); reverse(all(q)); reverse(all(a)); reverse(all(b)); Poly r(b.size() - 1); auto bq = multiply(b, q); for (int i = 0; i < (int)r.size(); ++i) { r[i] = a[i] - bq[i]; } return {q, r}; } virtual Poly multipoint(Poly p, const vector<outer_type>& x) { vector<Poly> seg_prods; seg_prods.reserve(2 * (int)x.size() - 1); function<void(int, int)> push_prods = [&](int l, int r) { if (r == l + 1) { seg_prods.push_back({-x[l], 1}); return; } int m = (l + r) / 2; push_prods(l, m); const auto& p = seg_prods.back(); push_prods(m, r); const auto& q = seg_prods.back(); // no reallocations because of reserve() seg_prods.push_back(multiply(p, q)); }; push_prods(0, x.size()); vector<outer_type> ans(x.size()); auto fill_ans = [&](const auto& self, int l, int r, Poly p) { p = divmod(p, seg_prods.back()).second; seg_prods.pop_back(); if (r <= l + 64) { for (int i = l; i < r; ++i) { outer_type& res = ans[i]; for (int j = (int)p.size() - 1; j >= 0; --j) { res = res * x[i] + p[j]; } } for (int i = l; i < r - 1; ++i) { seg_prods.pop_back(); seg_prods.pop_back(); } return; } int m = (l + r) / 2; self(self, m, r, p); self(self, l, m, p); }; fill_ans(fill_ans, 0, x.size(), p); return ans; } protected: static constexpr int L = 31 - __builtin_clz(N); static_assert(!(N & (N - 1))); vector<inner_type> angles; vector<int> bitrev; bool initialized_; void initialize() { fill_angles(); fill_bitrev(); initialized_ = true; } virtual void fill_angles() = 0; void fill_bitrev() { bitrev.assign(N, 0); for (int i = 0; i < N; ++i) { for (int j = 0; j < L; ++j) { bitrev[i] = (bitrev[i] << 1) | !!(i & (1 << j)); } } } void butterfly(vector<inner_type>& a) { if (!initialized_) { initialize(); } const int n = a.size(); assert(!(n & (n - 1))); const int l = __builtin_ctz(n); for (int i = 0; i < n; ++i) { int j = revbit(i, l); if (j > i) { swap(a[i], a[j]); } } } int revbit(int num, int len) const { return bitrev[num] >> (L - len); } virtual void fft(vector<inner_type>& a) { if (!initialized_) { initialize(); } const int n = a.size(); assert(!(n & (n - 1))); butterfly(a); for (int len = 1; len < n; len *= 2) { for (int start = 0; start < n; start += 2 * len) { for (int i = 0; i < len; ++i) { const auto w = angles[N / 2 / len * i]; const auto x = a[start + i], y = a[start + len + i] * w; a[start + i] = x + y; a[start + len + i] = x - y; } } } } void ifft(vector<inner_type>& a) { fft(a); for (auto& x : a) { x /= a.size(); } reverse(1 + all(a)); } }; template <int mod, int N = (1 << __builtin_ctz(mod - 1))> class NTT : public IFFT<Modular<mod>, Modular<mod>, N> { using Mint = Modular<mod>; using Poly = vector<Mint>; using IFFT<Modular<mod>, Modular<mod>, N>::angles; using IFFT<Modular<mod>, Modular<mod>, N>::multiply; using IFFT<Modular<mod>, Modular<mod>, N>::divmod; using IFFT<Modular<mod>, Modular<mod>, N>::fft; using IFFT<Modular<mod>, Modular<mod>, N>::ifft; using IFFT<Modular<mod>, Modular<mod>, N>::butterfly; protected: void fill_angles() { vector<int> primes; for (int x = mod - 1, p = 2; x > 1; ++p) { if (p * p > x) { primes.push_back(x); break; } if (x % p == 0) { primes.push_back(p); while (x % p == 0) { x /= p; } } } auto isPrimitiveRoot = [&](Mint g) { for (int p : primes) { if (g.pow(mod / p) == 1) { return false; } } return true; }; int g = 2; while (!isPrimitiveRoot(g)) { ++g; } g = Mint(g).pow(mod / N).val; this->angles.assign(N, 1); for (int i = 1; i < N; ++i) { this->angles[i] = this->angles[i - 1] * g; } assert(this->angles.back() * g == 1); } void ntt(vector<Mint>& a) { fft(a); } public: void double_under_fft(vector<Mint>& a) { const int n = a.size(); assert(!(n & (n - 1))); auto b = a; butterfly(b); ifft(b); for (int i = 0; i < n; ++i) { b[i] *= angles[N / n / 2 * i]; } fft(b); butterfly(b); a.resize(n + n); copy(all(b), a.begin() + n); } Poly multipoint(Poly p, const vector<Mint>& x) { vector<Poly> seg_prods; seg_prods.reserve(2 * (int)x.size() - 1); function<void(int, int)> push_prods = [&](int l, int r) { if (r == l + 1) { seg_prods.push_back({-x[l] + 1, -x[l] - 1}); return; } int m = (l + r) / 2; push_prods(l, m); auto p = seg_prods.back(); push_prods(m, r); auto q = seg_prods.back(); if (p.size() == q.size()) { double_under_fft(p); double_under_fft(q); } else { double_under_fft(p); ifft(q); q.resize(p.size(), 0); fft(q); } for (int i = 0; i < (int)p.size(); ++i) { p[i] *= q[i]; } seg_prods.push_back(p); }; push_prods(0, x.size()); for (auto& v : seg_prods) { butterfly(v); ifft(v); while (v.back() == 0) { v.pop_back(); } } vector<Mint> ans(x.size()); auto fill_ans = [&](const auto& self, int l, int r, Poly p) { p = divmod(p, seg_prods.back()).second; seg_prods.pop_back(); if (r <= l + 64) { for (int i = l; i < r; ++i) { Mint& res = ans[i]; for (int j = (int)p.size() - 1; j >= 0; --j) { res = res * x[i] + p[j]; } } for (int i = l; i < r - 1; ++i) { seg_prods.pop_back(); seg_prods.pop_back(); } return; } int m = (l + r) / 2; self(self, m, r, p); self(self, l, m, p); }; fill_ans(fill_ans, 0, x.size(), p); return ans; } }; using li = long long; using LI = __int128_t; using ld = long double; using uint = unsigned int; using ull = unsigned long long; ostream& operator <<(ostream& ostr, LI x) { static constexpr li BIG = 1e18; if (x < 0) { ostr << "-"; x = -x; } if (x < BIG) { return ostr << (li)x; } else if (x / BIG >= BIG) { stringstream ss; ss << setfill('0') << setw(18) << (li)(x / BIG % BIG); ss << setfill('0') << setw(18) << (li)(x % BIG); return ostr << (li)(x / BIG / BIG) << ss.str(); } else { stringstream ss; ss << setfill('0') << setw(18) << (li)(x % BIG); return ostr << (li)(x / BIG) << ss.str(); } } template <typename T> ostream& operator <<(ostream& ostr, const vector<T>& vec) { auto [pre, sep, post] = (&ostr == &cout) ? make_tuple("", " ", "") : make_tuple("[", ", ", "]"); ostr << pre; bool fp = true; for (const auto& x : vec) { if (fp) { fp = false; } else { ostr << sep; } ostr << x; } return ostr << post; } template <typename T, size_t N> ostream& operator <<(ostream& ostr, const array<T, N>& vec) { auto [pre, sep, post] = (&ostr == &cout) ? make_tuple("", " ", "") : make_tuple("[", ", ", "]"); ostr << pre; bool fp = true; for (const auto& x : vec) { if (fp) { fp = false; } else { ostr << sep; } ostr << x; } return ostr << post; } template <typename T> ostream& operator <<(ostream& ostr, const set<T>& st) { auto [pre, sep, post] = (&ostr == &cout) ? make_tuple("", " ", "") : make_tuple("{", ", ", "}"); ostr << pre; bool fp = true; for (const auto& x : st) { if (fp) { fp = false; } else { ostr << sep; } ostr << x; } return ostr << post; } template <typename T> ostream& operator <<(ostream& ostr, const multiset<T>& st) { auto [pre, sep, post] = (&ostr == &cout) ? make_tuple("", " ", "") : make_tuple("{", ", ", "}"); ostr << pre; bool fp = true; for (const auto& x : st) { if (fp) { fp = false; } else { ostr << sep; } ostr << x; } return ostr << post; } template <typename T, typename U> ostream& operator <<(ostream& ostr, const map<T, U>& mp) { ostr << "{"; bool fp = true; for (const auto& [k, v] : mp) { if (fp) { fp = false; } else { ostr << ", "; } ostr << k << ": " << v; } return ostr << "}"; } template <typename T, typename U> ostream& operator <<(ostream& ostr, const pair<T, U>& p) { return ostr << "(" << p.first << ", " << p.second << ")"; } #define all(x) (x).begin(), (x).end() int nxt() { int x; cin >> x; return x; } constexpr int mod = 998'244'353; using Mint = Modular<mod>; NTT<mod, (1 << 18)> ntt; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); vector<Mint> p(nxt()), x(nxt()); cin >> p >> x; cout << ntt.multipoint(p, x) << "\n"; return 0; }