Submit Info #58282

Problem Lang User Status Time Memory
Log of Formal Power Series cpp kaage AC 634 ms 46.93 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.42 MiB
max_all_zero_00 AC 506 ms 46.89 MiB
max_random_00 AC 598 ms 46.93 MiB
max_random_01 AC 634 ms 46.87 MiB
max_random_02 AC 631 ms 46.87 MiB
max_random_03 AC 598 ms 46.92 MiB
max_random_04 AC 601 ms 46.88 MiB
near_262144_00 AC 293 ms 23.46 MiB
near_262144_01 AC 296 ms 23.38 MiB
near_262144_02 AC 489 ms 38.43 MiB
random_00 AC 549 ms 42.36 MiB
random_01 AC 582 ms 46.10 MiB
random_02 AC 65 ms 5.95 MiB
random_03 AC 567 ms 44.22 MiB
random_04 AC 501 ms 38.80 MiB
small_degree_00 AC 1 ms 0.42 MiB
small_degree_01 AC 1 ms 0.45 MiB
small_degree_02 AC 1 ms 0.45 MiB
small_degree_03 AC 1 ms 0.42 MiB
small_degree_04 AC 1 ms 0.45 MiB
small_degree_05 AC 1 ms 0.45 MiB
small_degree_06 AC 1 ms 0.43 MiB
small_degree_07 AC 1 ms 0.45 MiB
small_degree_08 AC 1 ms 0.45 MiB
small_degree_09 AC 1 ms 0.45 MiB

#line 1 "test/yosupo/log_of_formal_power_series.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/log_of_formal_power_series" #line 2 "other/template.hpp" #define _CRT_SECURE_NO_WARNINGS #ifndef __clang__ #ifdef ONLINE_JUDGE #ifdef _WIN64 #pragma GCC target("avx2") #else #pragma GCC target("avx512f") #endif #elif defined EVAL #else #pragma GCC target("avx2") #endif #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #endif #include <string.h> #include <algorithm> #include <array> #include <bitset> #include <cassert> #include <cfloat> #include <climits> #include <cmath> #include <complex> #include <ctime> #include <deque> #include <fstream> #include <functional> #include <iomanip> #include <iostream> #include <iterator> #include <list> #include <map> #include <memory> #include <queue> #include <random> #include <set> #include <stack> #include <string> #include <unordered_map> #include <unordered_set> #include <utility> #include <vector> #define rep(i, n) for (int i = 0; i < (n); i++) #define REP(i, n) for (int i = 1; i <= (n); i++) #define all(V) V.begin(), V.end() using i128 = __int128_t; using u128 = __uint128_t; using uint = unsigned int; using lint = long long; using ulint = unsigned long long; using IP = std::pair<int, int>; using LP = std::pair<lint, lint>; constexpr int INF = INT_MAX / 2; constexpr lint LINF = LLONG_MAX / 2; constexpr double eps = DBL_EPSILON * 10; constexpr double PI = 3.141592653589793238462643383279; template <class T> class prique : public std::priority_queue<T, std::vector<T>, std::greater<T>> { }; int popcount(uint x) { #if __cplusplus >= 202002L return std::popcount(x); #else #ifndef __clang__ return __builtin_popcount(x); #endif #endif x = (x & 0x55555555) + (x >> 1 & 0x55555555); x = (x & 0x33333333) + (x >> 2 & 0x33333333); x = (x & 0x0f0f0f0f) + (x >> 4 & 0x0f0f0f0f); x = (x & 0x00ff00ff) + (x >> 8 & 0x00ff00ff); return (x & 0x0000ffff) + (x >> 16 & 0x0000ffff); } template <class F> inline constexpr decltype(auto) lambda_fix(F&& f) { return [f = std::forward<F>(f)](auto&&... args) { return f(f, std::forward<decltype(args)>(args)...); }; } template <class T> constexpr std::vector<T> make_vec(size_t n) { return std::vector<T>(n); } template <class T, class... Args> constexpr auto make_vec(size_t n, Args&&... args) { return std::vector<decltype(make_vec<T>(args...))>( n, make_vec<T>(std::forward<Args>(args)...)); } template <class T, class U> std::istream& operator>>(std::istream& ist, std::pair<T, U>& x) { return ist >> x.first >> x.second; } template <class T, class U> std::ostream& operator<<(std::ostream& ost, const std::pair<T, U>& x) { return ost << x.first << " " << x.second; } template < class Container, std::enable_if_t<std::negation_v<std::is_same<Container, std::string>>, std::nullptr_t> = nullptr> auto operator>>(std::istream& ist, Container& cont) -> decltype(typename Container::iterator(), std::cin)& { std::vector<typename Container::value_type> tmp; while (true) { typename Container::value_type t; ist >> t; tmp.emplace_back(t); if (getchar() == '\n') break; } cont = Container(std::move(tmp)); return ist; } template <class Container, std::enable_if_t<!std::is_same_v<Container, std::string>, std::nullptr_t> = nullptr> auto operator<<(std::ostream& ost, const Container& cont) -> decltype(typename Container::iterator(), std::cout)& { for (auto it = cont.begin(); it != cont.end(); it++) { if (it != cont.begin()) ost << ' '; ost << *it; } return ost; } template <class Container> auto sum(const Container& cont) -> decltype(typename Container::iterator(), 0LL) { lint res = 0; for (auto it = cont.begin(); it != cont.end(); it++) res += *it; return res; } template <class T, class U> constexpr inline bool chmax(T& lhs, const U& rhs) noexcept { if (lhs < rhs) { lhs = rhs; return true; } return false; } template <class T, class U> constexpr inline bool chmin(T& lhs, const U& rhs) noexcept { if (lhs > rhs) { lhs = rhs; return true; } return false; } constexpr inline lint gcd(lint a, lint b) noexcept { while (b) { lint c = a; a = b; b = c % b; } return a; } inline lint lcm(lint a, lint b) noexcept { return a / gcd(a, b) * b; } constexpr bool isprime(lint n) noexcept { if (n == 1) return false; for (int i = 2; i * i <= n; i++) { if (n % i == 0) return false; } return true; } template <class T> constexpr T mypow(T a, lint b) noexcept { T res(1); while (true) { if (b & 1) res *= a; b >>= 1; if (!b) break; a *= a; } return res; } constexpr lint modpow(lint a, lint b, lint m) noexcept { a %= m; lint res(1); while (b) { if (b & 1) res *= a, res %= m; a *= a, a %= m, b >>= 1; } return res; } LP extGcd(lint a, lint b) noexcept { if (b == 0) return {1, 0}; LP s = extGcd(b, a % b); std::swap(s.first, s.second); s.second -= a / b * s.first; return s; } LP ChineseRem(const lint& b1, const lint& m1, const lint& b2, const lint& m2) noexcept { auto p = extGcd(m1, m2); lint g = gcd(m1, m2), l = m1 / g * m2; lint tmp = (b2 - b1) / g * p.first % (m2 / g); lint r = (b1 + m1 * tmp + l) % l; return {r, l}; } int LCS(const std::string& a, const std::string& b) { auto dp = make_vec<int>(a.size() + 1, b.size() + 1); rep(i, a.size()) { rep(j, b.size()) { chmax(dp[i + 1][j], dp[i][j]); chmax(dp[i][j + 1], dp[i][j]); if (a[i] == b[j]) chmax(dp[i + 1][j + 1], dp[i][j] + 1); } chmax(dp[i + 1][b.size()], dp[i][b.size()]); } rep(j, b.size()) chmax(dp[a.size()][j + 1], dp[a.size()][j]); return dp[a.size()][b.size()]; } template <class T, std::enable_if_t<std::is_convertible<int, T>::value, std::nullptr_t> = nullptr> void compress(std::vector<T>& vec) { auto tmp = vec; std::sort(all(tmp)); tmp.erase(std::unique(all(tmp)), tmp.end()); for (T& i : vec) i = std::lower_bound(all(tmp), i) - tmp.begin(); } template <class T> void compress(T* l, T* r) { std::vector<T> tmp(l, r); std::sort(all(tmp)); tmp.erase(std::unique(all(tmp)), tmp.end()); for (auto i = l; i < r; i++) { *i = std::lower_bound(all(tmp), *i) - tmp.begin(); } } template <class InputIter> void compress(InputIter l, InputIter r) { std::vector<typename InputIter::value_type> tmp(l, r); std::sort(all(tmp)); tmp.erase(std::unique(all(tmp)), tmp.end()); for (auto i = l; i < r; i++) { *i = std::lower_bound(all(tmp), *i) - tmp.begin(); } } #line 3 "other/type_traits.hpp" class ModInt__Base {}; class StaticModInt__Base : ModInt__Base {}; class DynamicModInt__Base : ModInt__Base {}; template <class T> class is_ModInt : public std::is_base_of<ModInt__Base, T> {}; template <class T> constexpr bool is_ModInt_v = is_ModInt<T>::value; template <class T> class is_StaticModInt : public std::is_base_of<StaticModInt__Base, T> {}; template <class T> constexpr bool is_StaticModInt_v = is_StaticModInt<T>::value; template <class T> class is_DynamicModInt : public std::is_base_of<DynamicModInt__Base, T> {}; template <class T> constexpr bool is_DynamicModInt_v = is_DynamicModInt<T>::value; #line 4 "math/StaticModInt.hpp" template <int modulo> class StaticModInt : StaticModInt__Base { std::conditional_t<(modulo > (INT_MAX >> 1)), lint, int> value; static constexpr int inv1000000007[] = {0, 1, 500000004, 333333336, 250000002, 400000003, 166666668, 142857144, 125000001, 111111112, 700000005}, inv998244353[] = {0, 1, 499122177, 332748118, 748683265, 598946612, 166374059, 855638017, 873463809, 443664157, 299473306}; public: static constexpr int mod_value = modulo; constexpr StaticModInt() : value(0) {} template <class T, std::enable_if_t<!std::is_convertible<T, StaticModInt>::value, std::nullptr_t> = nullptr> constexpr StaticModInt(T value = 0) : value(value % int(modulo)) { if (this->value < 0) this->value += modulo; } inline constexpr StaticModInt inv() const { if constexpr (modulo == 1000000007) { if (*this <= 10) return inv1000000007[*this]; } else if constexpr (modulo == 998244353) { if (*this <= 10) return inv998244353[*this]; } return mypow(*this, modulo - 2); } inline constexpr operator int() const { return value; } inline constexpr StaticModInt& operator+=(const StaticModInt& x) { value = value + x.value; if (value >= modulo) value -= modulo; return *this; } inline constexpr StaticModInt& operator++() { if (value == modulo - 1) value = 0; else value++; return *this; } inline constexpr StaticModInt operator++(int) { StaticModInt res = *this; ++*this; return res; } inline constexpr StaticModInt operator-() const { return StaticModInt(0) -= *this; } inline constexpr StaticModInt& operator-=(const StaticModInt& x) { if (value < x.value) value += modulo; value -= x.value; return *this; } inline constexpr StaticModInt& operator--() { if (value == 0) value = modulo - 1; else value--; return *this; } inline constexpr StaticModInt operator--(int) { StaticModInt res = *this; --*this; return res; } inline constexpr StaticModInt& operator*=(const StaticModInt& x) { value = (ulint)value * x.value % modulo; return *this; } inline constexpr StaticModInt& operator/=(const StaticModInt& rhs) { return *this *= rhs.inv(); } template <class T> constexpr StaticModInt operator+(const T& rhs) const { return StaticModInt(*this) += rhs; } template <class T> constexpr StaticModInt& operator+=(const T& rhs) { return operator+=(StaticModInt(rhs)); } template <class T> constexpr StaticModInt operator-(const T& rhs) const { return StaticModInt(*this) -= rhs; } template <class T> constexpr StaticModInt& operator-=(const T& rhs) { return operator-=(StaticModInt(rhs)); } template <class T> constexpr StaticModInt operator*(const T& rhs) const { return StaticModInt(*this) *= rhs; } template <class T> constexpr StaticModInt& operator*=(const T& rhs) { return operator*=(StaticModInt(rhs)); } template <class T> constexpr StaticModInt operator/(const T& rhs) const { return StaticModInt(*this) /= rhs; } template <class T> constexpr StaticModInt& operator/=(const T& rhs) { return operator/=(StaticModInt(rhs)); } static int primitive_root() { static int p = 0; static std::random_device rd; static std::mt19937 mt(rd()); static std::uniform_int_distribution<> uid(1, modulo - 1); if (p) return 0; // use naive factorize due to file size limit std::vector<int> vec; int tmp = modulo - 1; for (int i = 2; i * i <= tmp; i++) { if (tmp % i == 0) { vec.emplace_back(i); do { tmp /= i; } while (tmp % i == 0); } } if (tmp != 1) vec.emplace_back(tmp); while (true) { p = uid(mt); bool f = true; for (const auto& i : vec) { if (mypow(StaticModInt(p), (modulo - 1) / i) == 1) { f = false; break; } } if (f) return p; } } }; template <int modulo> std::istream& operator>>(std::istream& ist, StaticModInt<modulo>& x) { lint a; ist >> a; x = a; return ist; } /** * @title StaticModInt */ #line 4 "math/NumberTheoreticTransform.hpp" // 1012924417, 5, 2^21 // 924844033, 5, 2^21 // 998244353, 3, 2^23 // 1224736769, 3, 2^24 // 167772161, 3, 2^25 // 469762049, 3, 2^26 class NumberTheoreticTransform { static constexpr int bases[] = {1012924417, 924844033, 998244353, 1224736769, 167772161, 469762049}; static constexpr int roots[] = {5, 5, 3, 3, 3, 3}; private: template <int modulo> static void ntt(std::vector<StaticModInt<modulo>>& a, StaticModInt<modulo> root) { int sz = a.size(); if (sz == 1) return; if (inverse) root = mypow(root, modulo - 1 - (modulo - 1) / sz); else root = mypow(root, (modulo - 1) / sz); std::vector<StaticModInt<modulo>> b(sz), roots((sz >> 1) + 1, 1); rep(i, sz >> 1) roots[i + 1] = roots[i] * root; for (int i = sz >> 1, w = 1; w < sz; i >>= 1, w <<= 1) { for (int j = 0; j < i; j++) { for (int k = 0; k < w; k++) { b[k + ((w * j) << 1)] = a[k + w * j] + a[k + w * j + (sz >> 1)]; b[k + ((w * j) << 1) + w] = roots[w * j] * (a[k + w * j] - a[k + w * j + (sz >> 1)]); } } std::swap(a, b); } } template <class T, int modulo> static std::vector<StaticModInt<modulo>> internal_convolution( const std::vector<T>& f_, const std::vector<T>& g_, StaticModInt<modulo> root) { std::vector<StaticModInt<modulo>> f(f_.size()), g(g_.size()); rep(j, f_.size()) f[j] = f_[j]; rep(j, g_.size()) g[j] = g_[j]; return internal_convolution(f, g, root); } template <int modulo> static std::vector<StaticModInt<modulo>> internal_convolution( std::vector<StaticModInt<modulo>> f, std::vector<StaticModInt<modulo>> g, StaticModInt<modulo> root) { size_t target_size = f.size() + g.size() - 1, sz = 1; while (sz < f.size() + g.size()) sz <<= 1; f.resize(sz), g.resize(sz); inverse = false; ntt(f, root), ntt(g, root); rep(i, f.size()) f[i] *= g[i]; inverse = true; ntt(f, root); StaticModInt<modulo> inv = StaticModInt<modulo>(f.size()).inv(); rep(i, f.size()) f[i] *= inv; f.resize(target_size); return f; } public: static bool inverse; template <int modulo, class T> static std::vector<StaticModInt<modulo>> convolution( const std::vector<T>& f, const std::vector<T>& g) { if constexpr (modulo == bases[0] || modulo == bases[1] || modulo == bases[2] || modulo == bases[3] || modulo == bases[4] || modulo == bases[5]) { std::vector<StaticModInt<modulo>> f_(f.size()), g_(g.size()); rep(i, f.size()) f_[i] = f[i]; rep(i, g.size()) g_[i] = g[i]; if constexpr (modulo == bases[0]) { return internal_convolution<modulo>( f_, g_, StaticModInt<modulo>(roots[0])); } else if constexpr (modulo == bases[1]) { return internal_convolution<modulo>( f_, g_, StaticModInt<modulo>(roots[1])); } else if constexpr (modulo == bases[2]) { return internal_convolution<modulo>( f_, g_, StaticModInt<modulo>(roots[2])); } else if constexpr (modulo == bases[3]) { return internal_convolution<modulo>( f_, g_, StaticModInt<modulo>(roots[3])); } else if constexpr (modulo == bases[4]) { return internal_convolution<modulo>( f_, g_, StaticModInt<modulo>(roots[4])); } else { return internal_convolution<modulo>( f_, g_, StaticModInt<modulo>(roots[5])); } } constexpr int base1 = 998244353, base2 = 1224736769, base3 = 469762049; auto re1 = internal_convolution<T, base1>(f, g, 3); auto re2 = internal_convolution<T, base2>(f, g, 3); auto re3 = internal_convolution<T, base3>(f, g, 3); std::vector<StaticModInt<modulo>> res(re1.size()); constexpr int r12 = StaticModInt<base2>(base1).inv(); constexpr int r13 = StaticModInt<base3>(base1).inv(); constexpr int r23 = StaticModInt<base3>(base2).inv(); rep(i, re1.size()) { re2[i] = StaticModInt<base2>(re2[i] - re1[i]) * r12; re3[i] = (StaticModInt<base3>(re3[i] - re1[i]) * r13 - re2[i]) * r23; res[i] = (StaticModInt<modulo>(re1[i]) + StaticModInt<modulo>(re2[i]) * base1 + StaticModInt<modulo>(re3[i]) * base1 * base2); } return res; } template <int modulo> static std::vector<StaticModInt<modulo>> convolution( std::vector<StaticModInt<modulo>> f, std::vector<StaticModInt<modulo>> g) { if constexpr (modulo == bases[0] || modulo == bases[1] || modulo == bases[2] || modulo == bases[3] || modulo == bases[4] || modulo == bases[5]) { std::vector<StaticModInt<modulo>> f_(f.size()), g_(g.size()); rep(i, f.size()) f_[i] = f[i]; rep(i, g.size()) g_[i] = g[i]; if constexpr (modulo == bases[0]) { return internal_convolution<modulo>( f_, g_, StaticModInt<modulo>(roots[0])); } else if constexpr (modulo == bases[1]) { return internal_convolution<modulo>( f_, g_, StaticModInt<modulo>(roots[1])); } else if constexpr (modulo == bases[2]) { return internal_convolution<modulo>( f_, g_, StaticModInt<modulo>(roots[2])); } else if constexpr (modulo == bases[3]) { return internal_convolution<modulo>( f_, g_, StaticModInt<modulo>(roots[3])); } else if constexpr (modulo == bases[4]) { return internal_convolution<modulo>( f_, g_, StaticModInt<modulo>(roots[4])); } else { return internal_convolution<modulo>( f_, g_, StaticModInt<modulo>(roots[5])); } } constexpr int base1 = 998244353, base2 = 1224736769, base3 = 469762049; auto re1 = internal_convolution<StaticModInt<modulo>, base1>( f, g, StaticModInt<base1>(3)); auto re2 = internal_convolution<StaticModInt<modulo>, base2>( f, g, StaticModInt<base2>(3)); auto re3 = internal_convolution<StaticModInt<modulo>, base3>( f, g, StaticModInt<base3>(3)); std::vector<StaticModInt<modulo>> res(re1.size()); constexpr int r12 = StaticModInt<base2>(base1).inv(); constexpr int r13 = StaticModInt<base3>(base1).inv(); constexpr int r23 = StaticModInt<base3>(base2).inv(); rep(i, re1.size()) { re2[i] = StaticModInt<base2>(re2[i] - re1[i]) * r12; re3[i] = (StaticModInt<base3>(re3[i] - re1[i]) * r13 - re2[i]) * r23; res[i] = (StaticModInt<modulo>(re1[i]) + StaticModInt<modulo>(re2[i]) * base1 + StaticModInt<modulo>(re3[i]) * base1 * base2); } return res; } template <class T> static std::vector<lint> convolution_plain(std::vector<T> f, std::vector<T> g) { const int mod1 = 998244353, mod2 = 1224736769; std::vector<StaticModInt<mod1>> mul1 = internal_convolution<mod1>(f, g, 3); std::vector<StaticModInt<mod2>> mul2 = internal_convolution<mod2>(f, g, 3); std::vector<lint> res(mul1.size()); rep(i, mul1.size()) res[i] = ChineseRem(mul1[i], mod1, mul2[i], mod2).first; return res; } }; bool NumberTheoreticTransform::inverse = false; /** * @title NumberTheoreticTransform */ #line 4 "math/FormalPowerSeries.hpp" template <class T, std::enable_if_t<is_ModInt_v<T>, std::nullptr_t> = nullptr> class FormalPowerSeries { private: std::vector<T> vec; using NTT = NumberTheoreticTransform; using FPS = FormalPowerSeries<T>; public: template <class... Args> FormalPowerSeries(Args&&... args) : vec(std::forward<Args>(args)...) {} operator std::vector<T>() { return vec; } operator std::vector<T>() const { return vec; } FPS operator-() const { FPS res(*this); for (T& i : res.vec) i = -i; return res; } template <class U> FPS& operator+=(const U& v) { if (vec.empty()) vec.emplace_back(v); else vec[0] += v; return *this; } template <class U> FPS operator+(const U& v) const { FPS res(*this); return res += v; } FPS operator+=(const FPS& f) { vec = NTT::convolution(vec, f.vec); return *this; } FPS operator+(const FPS& f) const { FPS res(*this); return res += f; } template <class U> FPS& operator-=(const U& v) { return *this += -v; } template <class U> FPS& operator*=(const U& v) { for (const T& i : vec) i *= v; return *this; } template <class U> FPS operator*(const U& v) { FPS res(*this); return res *= v; } FPS operator*=(const FPS& f) { vec = NTT::convolution(vec, f.vec); return *this; } FPS operator*(const FPS& f) { FPS res(*this); return res *= f; } template <class U> FPS& operator/=(const U& v) { for (const T& i : vec) i /= v; return *this; } template <class U> FPS operator/(const U& v) { FPS res(*this); return res /= v; } FPS operator/=(const FPS& f) { vec = NTT::convolution(vec, f.inverse().vec); return *this; } FPS operator/(const FPS& f) { FPS res(*this); return res /= f; } template <class U> [[nodiscard]] size_t size() const { return vec.size(); } void resize(size_t n) { vec.resize(n); } void differentiate() { vec.erase(vec.begin()); REP(i, vec.size()) vec[i - 1] *= i; } [[nodiscard]] FPS differential() { FPS res = *this; res.differentiate(); return res; } void integrate() { vec.insert(vec.begin(), 0); REP(i, vec.size() - 1) vec[i] /= i; } [[nodiscard]] FPS integral() { FPS res = *this; res.integrate(); return res; } void invert() { invert(vec.size()); } void invert(size_t len) { *this = FPS(len); } [[nodiscard]] FPS inverse() const { return inverse(vec.size()); } [[nodiscard]] FPS inverse(size_t len) const { FPS res(1, T(1) / vec[0]); size_t n = 1; std::vector<T> vec_shortened = {vec[0]}; vec_shortened.reserve(len); while (n < len) { n <<= 1; vec_shortened.insert(vec_shortened.end(), vec.begin() + vec_shortened.size(), vec.begin() + std::min(vec.size(), n)); res *= -FPS(NTT::convolution(res.vec, vec_shortened)) + 2; res.resize(std::min(n, len)); } return FPS(std::move(res)); } [[nodiscard]] FPS log() { return log(vec.size()); } [[nodiscard]] FPS log(size_t len) { FPS differentiated = differential(); FPS tmp = differentiated / *this; tmp.resize(len - 1); return tmp.integral(); } [[nodiscard]] FPS exp() { return exp(vec.size()); } [[nodiscard]] FPS exp(size_t len) { std::vector<T> res = {1}; size_t n = 1; while (n < len) { n <<= 1; } } template <class U> friend std::ostream& operator<<(std::ostream&, const FormalPowerSeries<U>&); }; template <class T> std::ostream& operator<<(std::ostream& ost, const FormalPowerSeries<T>& fps) { ost << fps.vec; return ost; } #line 5 "test/yosupo/log_of_formal_power_series.test.cpp" using ModInt = StaticModInt<998244353>; using FPS = FormalPowerSeries<ModInt>; int main() { int N; std::vector<ModInt> vec; std::cin >> N >> vec; std::cout << FPS(std::move(vec)).log() << std::endl; }