Submit Info #39796

Problem Lang User Status Time Memory
Log of Formal Power Series cpp FlowerOfSorrow AC 793 ms 23.60 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.67 MiB
max_all_zero_00 AC 709 ms 23.54 MiB
max_random_00 AC 785 ms 23.59 MiB
max_random_01 AC 787 ms 23.59 MiB
max_random_02 AC 786 ms 23.52 MiB
max_random_03 AC 793 ms 23.54 MiB
max_random_04 AC 786 ms 23.60 MiB
near_262144_00 AC 376 ms 12.00 MiB
near_262144_01 AC 381 ms 12.05 MiB
near_262144_02 AC 617 ms 18.05 MiB
random_00 AC 749 ms 19.90 MiB
random_01 AC 777 ms 22.85 MiB
random_02 AC 83 ms 3.21 MiB
random_03 AC 767 ms 20.60 MiB
random_04 AC 708 ms 18.12 MiB
small_degree_00 AC 1 ms 0.67 MiB
small_degree_01 AC 1 ms 0.67 MiB
small_degree_02 AC 1 ms 0.62 MiB
small_degree_03 AC 1 ms 0.65 MiB
small_degree_04 AC 1 ms 0.65 MiB
small_degree_05 AC 3 ms 0.62 MiB
small_degree_06 AC 1 ms 0.66 MiB
small_degree_07 AC 1 ms 0.68 MiB
small_degree_08 AC 1 ms 0.64 MiB
small_degree_09 AC 2 ms 0.67 MiB

#include <bits/stdc++.h> using namespace std; template<typename T> struct Z_p{ using Type = typename decay<decltype(T::value)>::type; static vector<Type> MOD_INV; constexpr Z_p(): value(){ } template<typename U> Z_p(const U &x){ value = normalize(x); } template<typename U> static Type normalize(const U &x){ Type v; if(-mod() <= x && x < mod()) v = static_cast<Type>(x); else v = static_cast<Type>(x % mod()); if(v < 0) v += mod(); return v; } const Type& operator()() const{ return value; } template<typename U> explicit operator U() const{ return static_cast<U>(value); } constexpr static Type mod(){ return T::value; } Z_p &operator+=(const Z_p &otr){ if((value += otr.value) >= mod()) value -= mod(); return *this; } Z_p &operator-=(const Z_p &otr){ if((value -= otr.value) < 0) value += mod(); return *this; } template<typename U> Z_p &operator+=(const U &otr){ return *this += Z_p(otr); } template<typename U> Z_p &operator-=(const U &otr){ return *this -= Z_p(otr); } Z_p &operator++(){ return *this += 1; } Z_p &operator--(){ return *this -= 1; } Z_p operator++(int){ Z_p result(*this); *this += 1; return result; } Z_p operator--(int){ Z_p result(*this); *this -= 1; return result; } Z_p operator-() const{ return Z_p(-value); } template<typename U = T> typename enable_if<is_same<typename Z_p<U>::Type, int>::value, Z_p>::type &operator*=(const Z_p& rhs){ #ifdef _WIN32 uint64_t x = static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value); uint32_t xh = static_cast<uint32_t>(x >> 32), xl = static_cast<uint32_t>(x), d, m; asm( "divl %4; \n\t" : "=a" (d), "=d" (m) : "d" (xh), "a" (xl), "r" (mod()) ); value = m; #else value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value)); #endif return *this; } template<typename U = T> typename enable_if<is_same<typename Z_p<U>::Type, int64_t>::value, Z_p>::type &operator*=(const Z_p &rhs){ int64_t q = static_cast<int64_t>(static_cast<long double>(value) * rhs.value / mod()); value = normalize(value * rhs.value - q * mod()); return *this; } template<typename U = T> typename enable_if<!is_integral<typename Z_p<U>::Type>::value, Z_p>::type &operator*=(const Z_p &rhs){ value = normalize(value * rhs.value); return *this; } Z_p &operator^=(long long e){ if(e < 0) *this = 1 / *this, e = -e; Z_p res = 1; for(; e; *this *= *this, e >>= 1) if(e & 1) res *= *this; return *this = res; } Z_p operator^(long long e) const{ return Z_p(*this) ^= e; } Z_p &operator/=(const Z_p &otr){ Type a = otr.value, m = mod(), u = 0, v = 1; if(a < (int)MOD_INV.size()) return *this *= MOD_INV[a]; while(a){ Type t = m / a; m -= t * a; swap(a, m); u -= t * v; swap(u, v); } assert(m == 1); return *this *= u; } template<typename U> friend const Z_p<U> &abs(const Z_p<U> &v){ return v; } Type value; }; template<typename T> bool operator==(const Z_p<T> &lhs, const Z_p<T> &rhs){ return lhs.value == rhs.value; } template<typename T, typename U, typename enable_if<is_integral<U>::value>::type* = nullptr> bool operator==(const Z_p<T>& lhs, U rhs){ return lhs == Z_p<T>(rhs); } template<typename T, typename U, typename enable_if<is_integral<U>::value>::type* = nullptr> bool operator==(U lhs, const Z_p<T> &rhs){ return Z_p<T>(lhs) == rhs; } template<typename T> bool operator!=(const Z_p<T> &lhs, const Z_p<T> &rhs){ return !(lhs == rhs); } template<typename T, typename U, typename enable_if<is_integral<U>::value>::type* = nullptr> bool operator!=(const Z_p<T> &lhs, U rhs){ return !(lhs == rhs); } template<typename T, typename U, typename enable_if<is_integral<U>::value>::type* = nullptr> bool operator!=(U lhs, const Z_p<T> &rhs){ return !(lhs == rhs); } template<typename T> bool operator<(const Z_p<T> &lhs, const Z_p<T> &rhs){ return lhs.value < rhs.value; } template<typename T> bool operator>(const Z_p<T> &lhs, const Z_p<T> &rhs){ return lhs.value > rhs.value; } template<typename T> bool operator<=(const Z_p<T> &lhs, const Z_p<T> &rhs){ return lhs.value <= rhs.value; } template<typename T> bool operator>=(const Z_p<T> &lhs, const Z_p<T> &rhs){ return lhs.value >= rhs.value; } template<typename T> Z_p<T> operator+(const Z_p<T> &lhs, const Z_p<T> &rhs){ return Z_p<T>(lhs) += rhs; } template<typename T, typename U, typename enable_if<is_integral<U>::value>::type* = nullptr> Z_p<T> operator+(const Z_p<T> &lhs, U rhs){ return Z_p<T>(lhs) += rhs; } template<typename T, typename U, typename enable_if<is_integral<U>::value>::type* = nullptr> Z_p<T> operator+(U lhs, const Z_p<T> &rhs){ return Z_p<T>(lhs) += rhs; } template<typename T> Z_p<T> operator-(const Z_p<T> &lhs, const Z_p<T> &rhs){ return Z_p<T>(lhs) -= rhs; } template<typename T, typename U, typename enable_if<is_integral<U>::value>::type* = nullptr> Z_p<T> operator-(const Z_p<T>& lhs, U rhs){ return Z_p<T>(lhs) -= rhs; } template<typename T, typename U, typename enable_if<is_integral<U>::value>::type* = nullptr> Z_p<T> operator-(U lhs, const Z_p<T> &rhs){ return Z_p<T>(lhs) -= rhs; } template<typename T> Z_p<T> operator*(const Z_p<T> &lhs, const Z_p<T> &rhs){ return Z_p<T>(lhs) *= rhs; } template<typename T, typename U, typename enable_if<is_integral<U>::value>::type* = nullptr> Z_p<T> operator*(const Z_p<T>& lhs, U rhs){ return Z_p<T>(lhs) *= rhs; } template<typename T, typename U, typename enable_if<is_integral<U>::value>::type* = nullptr> Z_p<T> operator*(U lhs, const Z_p<T> &rhs){ return Z_p<T>(lhs) *= rhs; } template<typename T> Z_p<T> operator/(const Z_p<T> &lhs, const Z_p<T> &rhs) { return Z_p<T>(lhs) /= rhs; } template<typename T, typename U, typename enable_if<is_integral<U>::value>::type* = nullptr> Z_p<T> operator/(const Z_p<T>& lhs, U rhs) { return Z_p<T>(lhs) /= rhs; } template<typename T, typename U, typename enable_if<is_integral<U>::value>::type* = nullptr> Z_p<T> operator/(U lhs, const Z_p<T> &rhs) { return Z_p<T>(lhs) /= rhs; } template<typename T> istream &operator>>(istream &in, Z_p<T> &number){ typename common_type<typename Z_p<T>::Type, int64_t>::type x; in >> x; number.value = Z_p<T>::normalize(x); return in; } template<typename T> ostream &operator<<(ostream &out, const Z_p<T> &number){ return out << number(); } /* using ModType = int; struct VarMod{ static ModType value; }; ModType VarMod::value; ModType &mod = VarMod::value; using Zp = Z_p<VarMod>; */ constexpr int mod = (119 << 23) + 1; using Zp = Z_p<integral_constant<decay<decltype(mod)>::type, mod>>; template<typename T> vector<typename Z_p<T>::Type> Z_p<T>::MOD_INV; template<typename T = integral_constant<decay<decltype(mod)>::type, mod>> void precalc_inverse(int SZ){ auto &inv = Z_p<T>::MOD_INV; if(inv.empty()) inv.assign(2, 1); for(; inv.size() <= SZ; ) inv.push_back((mod - 1LL * mod / (int)inv.size() * inv[mod % (int)inv.size()]) % mod); } template<typename T> vector<T> precalc_power(T base, int SZ){ vector<T> res(SZ + 1, 1); for(auto i = 1; i <= SZ; ++ i) res[i] = res[i - 1] * base; return res; } // Requires modular template<class T, int root = 15311432, int root_pw = 1 << 23, int inv_root = 469870224> void number_theoric_transform(vector<T> &a, const bool invert = false){ int n = (int)a.size(); for(int i = 1, j = 0; i < n; ++ i){ int bit = n >> 1; for(; j & bit; bit >>= 1) j ^= bit; j ^= bit; if(i < j) swap(a[i], a[j]); } for(int len = 1; len < n; len <<= 1){ T wlen = invert ? inv_root : root; for(int i = len << 1; i < root_pw; i <<= 1) wlen *= wlen; for(int i = 0; i < n; i += len << 1){ T w = 1; for(int j = 0; j < len; ++ j, w *= wlen){ T u = a[i + j], v = a[i + j + len] * w; a[i + j] = u + v, a[i + j + len] = u - v; } } } if(invert){ T inv_n = T(1) / n; for(auto &x: a) x *= inv_n; } } // NTTmod: 998244353(2^23*7*17,3),754974721(2^24*3^2*5,11),469762049(2^26*7,3),167772161(2^25*5,3) template<class T> vector<T> convolute(vector<T> p, vector<T> q){ if(min(p.size(), q.size()) < 60){ vector<T> res((int)p.size() + (int)q.size() - 1); for(size_t i = 0; i < p.size(); ++ i) for(size_t j = 0; j < q.size(); ++ j) res[i + j] += p[i] * q[j]; return res; } int m = max((int)p.size() + (int)q.size() - 1, 1), n = m; if(__builtin_popcount(n) != 1) n = 1 << __lg(n) + 1; p.resize(n), q.resize(n); number_theoric_transform(p), number_theoric_transform(q); for(int i = 0; i < n; ++ i) p[i] *= q[i]; number_theoric_transform(p, true); p.resize(m); return p; } template<class T> // Requires number_theoric_transform, O(n log n) vector<T> operator*(const vector<T> &p, const vector<T> &q){ return convolute(p, q); } /* template<class T> // O(n m) vector<T> operator*(const vector<T> &a, const vector<T> &b){ if(a.empty() || b.empty()) return {}; vector<T> c(a.size() + b.size() - 1, 0); for(auto i = 0; i < (int)a.size(); ++ i) for(auto j = 0; j < (int)b.size(); ++ j) c[i + j] += a[i] * b[j]; return c; }*/ template<class T> vector<T> &operator*=(vector<T> &a, const vector<T> &b){ return a = a * b; } template<class T> vector<T> &operator+=(vector<T> &a, const vector<T> &b){ if(a.size() < b.size()) a.resize(b.size()); for(auto i = 0; i < (int)b.size(); ++ i) a[i] += b[i]; return a; } template<class T> vector<T> operator+(const vector<T> &a, const vector<T> &b){ vector<T> c = a; return c += b; } template<class T> vector<T> &operator-=(vector<T> &a, const vector<T> &b){ if(a.size() < b.size()) a.resize(b.size()); for(auto i = 0; i < (int)b.size(); ++ i) a[i] -= b[i]; return a; } template<class T> vector<T> operator-(const vector<T> &a, const vector<T> &b){ vector<T> c = a; return c -= b; } template<class T> vector<T> operator-(const vector<T> &a){ vector<T> c = a; for(auto i = 0; i < (int)c.size(); ++ i) c[i] = -c[i]; return c; } template<class T> vector<T> inverse(const vector<T> &a){ assert(!a.empty()); int n = (int)a.size(); vector<T> b = {1 / a[0]}; while((int)b.size() < n){ vector<T> a_cut(a.begin(), a.begin() + min(a.size(), b.size() << 1)), x = b * b * a_cut; b.resize(b.size() << 1); for(auto i = (int)b.size() >> 1; i < (int)min(x.size(), b.size()); ++ i) b[i] = -x[i]; } b.resize(n); return b; } template<class T> vector<T> &operator/=(vector<T> &a, const vector<T> &b){ int n = (int)a.size(), m = (int)b.size(); if(n < m) a.clear(); else{ vector<T> d = b; reverse(a.begin(), a.end()); reverse(d.begin(), d.end()); d.resize(n - m + 1); a *= inverse(d); a.erase(a.begin() + n - m + 1, a.end()); reverse(a.begin(), a.end()); } return a; } template<class T> vector<T> operator/(const vector<T> &a, const vector<T> &b){ vector<T> c = a; return c /= b; } template<class T> vector<T> &operator%=(vector<T> &a, const vector<T> &b){ int n = (int)a.size(), m = (int)b.size(); if(n >= m){ vector<T> c = (a / b) * b; a.resize(m - 1); for(auto i = 0; i < m - 1; ++ i) a[i] -= c[i]; } return a; } template<class T> vector<T> operator%(const vector<T> &a, const vector<T> &b){ vector<T> c = a; return c %= b; } template<class T, class U> vector<T> power(const vector<T> &a, const U &b, const vector<T> &c){ assert(b >= 0); vector<U> binary; U bb = b; while(bb > 0) binary.push_back(bb & 1), bb >>= 1; vector<T> res = vector<T>{1} % c; for(auto j = (int)binary.size() - 1; j >= 0; -- j){ res = res * res % c; if(binary[j] == 1) res = res * a % c; } return res; } template<class T> vector<T> derivative(const vector<T> &a){ vector<T> c = a; for(auto i = 0; i < (int)c.size(); ++ i) c[i] *= i; if(!c.empty()) c.erase(c.begin()); return c; } template<class T> vector<T> antiderivative(const vector<T> &a){ vector<T> c = a; c.insert(c.begin(), 0); for(auto i = 1; i < (int)c.size(); ++ i) c[i] /= i; return c; } template<class T> vector<T> logarithm(const vector<T> &a){ assert(!a.empty() && a[0] == 1); vector<T> u = antiderivative(derivative(a) * inverse(a)); u.resize(a.size()); return u; } template<class T> vector<T> exponential(const vector<T> &a){ assert(!a.empty() && a[0] == 0); int n = (int)a.size(); vector<T> b = {1}; while((int)b.size() < n){ vector<T> x(a.begin(), a.begin() + min(a.size(), b.size() << 1)); x[0] += 1; vector<T> old_b = b; b.resize(b.size() << 1); x -= logarithm(b); x *= old_b; for(auto i = (int)b.size() >> 1; i < (int)min(x.size(), b.size()); ++ i) b[i] = x[i]; } b.resize(n); return b; } template<class T> vector<T> sqrt(const vector<T> &a){ assert(!a.empty() && a[0] == 1); int n = (int)a.size(); vector<T> b = {1}; while((int)b.size() < n){ vector<T> x(a.begin(), a.begin() + min(a.size(), b.size() << 1)); b.resize(b.size() << 1); x *= inverse(b); T inv2 = 1 / static_cast<T>(2); for(auto i = (int)b.size() >> 1; i < (int)min(x.size(), b.size()); ++ i) b[i] = x[i] * inv2; } b.resize(n); return b; } template<class T> vector<T> multiply(const vector<vector<T>> &a){ if(a.empty()) return {0}; function<vector<T>(int, int)> mult = [&](int l, int r){ if(r - l == 1) return a[l]; int m = l + (r - l >> 1); return mult(l, m) * mult(m, r); }; return mult(0, (int)a.size()); } template<class T> T evaluate(const vector<T> &a, const T &x){ T res = {}; for(auto i = (int)a.size() - 1; i >= 0; -- i) res = res * x + a[i]; return res; } template<class T> vector<T> evaluate(const vector<T> &a, const vector<T> &x){ if(x.empty()) return {}; if(a.empty()) return vector<T>(x.size(), 0); int n = (int)x.size(); vector<vector<T>> st((n << 1) - 1); function<void(int, int, int)> build = [&](int u, int l, int r){ if(r - l == 1) st[u] = vector<T>{-x[l], 1}; else{ int m = l + (r - l >> 1), v = u + (m - l << 1); build(u + 1, l, m), build(v, m, r); st[u] = st[u + 1] * st[v]; } }; build(0, 0, n); vector<T> res(n); function<void(int, int, int, vector<T>)> eval = [&](int u, int l, int r, vector<T> f){ f %= st[u]; if((int)f.size() < 150){ for(auto i = l; i < r; ++ i) res[i] = evaluate(f, x[i]); return; } if(r - l == 1) res[l] = f[0]; else{ int m = l + (r - l >> 1), v = u + (m - l << 1); eval(u + 1, l, m, f), eval(v, m, r, f); } }; eval(0, 0, n, a); return res; } template<class T> vector<T> interpolate(const vector<T> &x, const vector<T> &y){ if(x.empty()) return { }; assert(x.size() == y.size()); int n = (int)x.size(); vector<vector<T>> st((n << 1) - 1); function<void(int, int, int)> build = [&](int u, int l, int r){ if(r - l == 1) st[u] = vector<T>{-x[l], 1}; else{ int m = l + (r - l >> 1), v = u + (m - l << 1); build(u + 1, l, m), build(v, m, r); st[u] = st[u + 1] * st[v]; } }; build(0, 0, n); vector<T> m = st[0], dm = derivative(m), val(n); function<void(int, int, int, vector<T>)> eval = [&](int u, int l, int r, vector<T> f){ f %= st[u]; if((int)f.size() < 150){ for(auto i = l; i < r; ++ i) val[i] = evaluate(f, x[i]); return; } if(r - l == 1) val[l] = f[0]; else{ int m = l + (r - l >> 1), v = u + (m - l << 1); eval(u + 1, l, m, f), eval(v, m, r, f); } }; eval(0, 0, n, dm); for(auto i = 0; i < n; ++ i) val[i] = y[i] / val[i]; function<vector<T>(int, int, int)> calc = [&](int u, int l, int r){ if(r - l == 1) return vector<T>{val[l]}; int m = l + (r - l >> 1), v = u + (m - l << 1); return calc(u + 1, l, m) * st[v] + calc(v, m, r) * st[u + 1]; }; return calc(0, 0, n); } // f[i] = 1^i + 2^i + ... + base^i template<class T> vector<T> faulhaber(const T &base, int n){ vector<T> ex(n + 1); T e = 1; for(auto i = 0; i <= n; ++ i) ex[i] = e, e /= i + 1; vector<T> den = ex; den.erase(den.begin()); for(auto &d : den) d = -d; vector<T> num(n); T p = 1; for(auto i = 0; i < n; ++ i) p *= base + 1, num[i] = ex[i + 1] * (1 - p); vector<T> res = num * inverse(den); res.resize(n); T f = 1; for(auto i = 0; i < n; ++ i) res[i] *= f, f *= i + 1; return res; } // (x + 1) * (x + 2) * ... * (x + n) // (can be optimized with precomputed inverses) template<class T> vector<T> sequence(int n){ if(n == 0) return {1}; if(n % 2 == 1) return sequence<T>(n - 1) * vector<T>{n, 1}; vector<T> c = sequence<T>(n / 2), a = c; reverse(a.begin(), a.end()); T f = 1; for(auto i = n / 2 - 1; i >= 0; -- i) f *= n / 2 - i, a[i] *= f; vector<T> b(n / 2 + 1); b[0] = 1; for(auto i = 1; i <= n / 2; ++ i) b[i] = b[i - 1] * (n / 2) / i; vector<T> h = a * b; h.resize(n / 2 + 1); reverse(h.begin(), h.end()); f = 1; for(auto i = 1; i <= n / 2; ++ i) f /= i, h[i] *= f; vector<T> res = c * h; return res; } template<class T> struct online_product{ const vector<T> a; vector<T> b, c; online_product(const vector<T> &a): a(a){ } T add(const T &val){ int i = (int)b.size(); b.push_back(val); if((int)c.size() <= i) c.resize(i + 1); c[i] += a[0] * b[i]; int z = 1; while((i & z - 1) == z - 1 && (int)a.size() > z){ vector<T> a_mul(a.begin() + z, a.begin() + min(z << 1, (int)a.size())); vector<T> b_mul(b.end() - z, b.end()); vector<T> c_mul = a_mul * b_mul; if((int)c.size() <= i + (int)c_mul.size()) c.resize(i + c_mul.size() + 1); for(auto j = 0; j < (int)c_mul.size(); ++ j) c[i + 1 + j] += c_mul[j]; z <<= 1; } return c[i]; } }; int main(){ cin.tie(0)->sync_with_stdio(0); cin.exceptions(ios::badbit | ios::failbit); int n; cin >> n; vector<Zp> p(n); for(auto i = 0; i < n; ++ i){ cin >> p[i]; } for(auto c: logarithm(p)){ cout << c << " "; } cout << "\n"; return 0; } /* */ //////////////////////////////////////////////////////////////////////////////////////// // // // Coded by Aeren // // // ////////////////////////////////////////////////////////////////////////////////////////