This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#define PROBLEM "https://judge.yosupo.jp/problem/inv_of_formal_power_series" #include <iostream> #include <atcoder/modint> #include "library/polynomial/formal_power_series_relaxed.hpp" using mint = atcoder::modint998244353; std::istream& operator>>(std::istream& in, mint &a) { long long e; in >> e; a = e; return in; } std::ostream& operator<<(std::ostream& out, const mint &a) { out << a.val(); return out; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; std::cin >> n; suisen::RelaxedInv<mint> inv_f; for (int i = 0; i < n; ++i) { mint v; std::cin >> v; std::cout << inv_f.append(v) << " \n"[i == n - 1]; } }
#line 1 "test/src/polynomial/formal_power_series_relaxed/inv_of_formal_power_series.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/inv_of_formal_power_series" #include <iostream> #include <atcoder/modint> #line 1 "library/polynomial/formal_power_series_relaxed.hpp" #include <atcoder/convolution> #line 1 "library/math/inv_mods.hpp" #include <vector> namespace suisen { template <typename mint> class inv_mods { public: inv_mods() = default; inv_mods(int n) { ensure(n); } const mint& operator[](int i) const { ensure(i); return invs[i]; } static void ensure(int n) { int sz = invs.size(); if (sz < 2) invs = { 0, 1 }, sz = 2; if (sz < n + 1) { invs.resize(n + 1); for (int i = sz; i <= n; ++i) invs[i] = mint(mod - mod / i) * invs[mod % i]; } } private: static std::vector<mint> invs; static constexpr int mod = mint::mod(); }; template <typename mint> std::vector<mint> inv_mods<mint>::invs{}; template <typename mint> std::vector<mint> get_invs(const std::vector<mint>& vs) { const int n = vs.size(); mint p = 1; for (auto& e : vs) { p *= e; assert(e != 0); } mint ip = p.inv(); std::vector<mint> rp(n + 1); rp[n] = 1; for (int i = n - 1; i >= 0; --i) { rp[i] = rp[i + 1] * vs[i]; } std::vector<mint> res(n); for (int i = 0; i < n; ++i) { res[i] = ip * rp[i + 1]; ip *= vs[i]; } return res; } } #line 1 "library/convolution/relaxed_convolution_ntt.hpp" #line 5 "library/convolution/relaxed_convolution_ntt.hpp" namespace suisen { // reference: https://qiita.com/Kiri8128/items/1738d5403764a0e26b4c template <typename mint> struct RelaxedConvolutionNTT { RelaxedConvolutionNTT(): _n(0), _f{}, _g{}, _h{} {} mint append(const mint& fi, const mint& gi) { static constexpr int threshold_log = 6; static constexpr int threshold = 1 << threshold_log; static constexpr int threshold_mask = threshold - 1; ++_n; _f.push_back(fi), _g.push_back(gi); const int q = _n >> threshold_log, r = _n & threshold_mask; if (r == 0) { if (q == (-q & q)) { std::vector<mint> f_fft = _f; std::vector<mint> g_fft = _g; f_fft.resize(2 * _n); g_fft.resize(2 * _n); atcoder::internal::butterfly(f_fft); atcoder::internal::butterfly(g_fft); std::vector<mint> h(2 * _n); for (int i = 0; i < 2 * _n; ++i) { h[i] = f_fft[i] * g_fft[i]; } atcoder::internal::butterfly_inv(h); ensure(2 * _n); const mint z = mint(2 * _n).inv(); for (int i = _n - 1; i < 2 * _n; ++i) { _h[i] += h[i] * z; } _f_fft.push_back(std::move(f_fft)); _g_fft.push_back(std::move(g_fft)); } else { const int log_q = __builtin_ctz(q); const int k = (-q & q) << threshold_log; std::vector<mint> f_fft(_f.end() - k, _f.end()); std::vector<mint> g_fft(_g.end() - k, _g.end()); f_fft.resize(2 * k); g_fft.resize(2 * k); atcoder::internal::butterfly(f_fft); atcoder::internal::butterfly(g_fft); std::vector<mint> h(2 * k); for (int i = 0; i < 2 * k; ++i) { h[i] = _f_fft[log_q + 1][i] * g_fft[i] + f_fft[i] * _g_fft[log_q + 1][i]; } atcoder::internal::butterfly_inv(h); const mint z = mint(2 * k).inv(); for (int i = 0; i < k; ++i) { _h[_n - 1 + i] += h[k - 1 + i] * z; } } } else { // naive convolve ensure(_n); for (int i = 0; i < r; ++i) { _h[_n - 1] += _f[i] * _g[_n - 1 - i]; } if (_n != r) { for (int i = 0; i < r; ++i) { _h[_n - 1] += _f[_n - i - 1] * _g[i]; } } } return _h[_n - 1]; } const mint& operator[](int i) const { return _h[i]; } std::vector<mint> get() const { return _h; } private: int _n; std::vector<mint> _f, _g, _h; std::vector<std::vector<mint>> _f_fft, _g_fft; void ensure(std::size_t n) { if (_h.size() < n) _h.resize(n); } }; } // namespace suisen #line 1 "library/math/modint_extension.hpp" #include <cassert> #include <optional> /** * refernce: https://37zigen.com/tonelli-shanks-algorithm/ * calculates x s.t. x^2 = a mod p in O((log p)^2). */ template <typename mint> std::optional<mint> safe_sqrt(mint a) { static int p = mint::mod(); if (a == 0) return std::make_optional(0); if (p == 2) return std::make_optional(a); if (a.pow((p - 1) / 2) != 1) return std::nullopt; mint b = 1; while (b.pow((p - 1) / 2) == 1) ++b; static int tlz = __builtin_ctz(p - 1), q = (p - 1) >> tlz; mint x = a.pow((q + 1) / 2); b = b.pow(q); for (int shift = 2; x * x != a; ++shift) { mint e = a.inv() * x * x; if (e.pow(1 << (tlz - shift)) != 1) x *= b; b *= b; } return std::make_optional(x); } /** * calculates x s.t. x^2 = a mod p in O((log p)^2). * if not exists, raises runtime error. */ template <typename mint> auto sqrt(mint a) -> decltype(mint::mod(), mint()) { return *safe_sqrt(a); } template <typename mint> auto log(mint a) -> decltype(mint::mod(), mint()) { assert(a == 1); return 0; } template <typename mint> auto exp(mint a) -> decltype(mint::mod(), mint()) { assert(a == 0); return 1; } template <typename mint, typename T> auto pow(mint a, T b) -> decltype(mint::mod(), mint()) { return a.pow(b); } template <typename mint> auto inv(mint a) -> decltype(mint::mod(), mint()) { return a.inv(); } #line 8 "library/polynomial/formal_power_series_relaxed.hpp" namespace suisen { template <typename mint> struct RelaxedInv { mint append(const mint& fi) { const int i = g.size(); if (i == 0) { assert(fi != 0); g.push_back(fi.inv()); } else { g.push_back(-g[0] * fg.append(fi, g[i - 1])); } return g.back(); } mint operator[](int i) const { return g[i]; } private: std::vector<mint> g; RelaxedConvolutionNTT<mint> fg; }; template <typename mint> struct RelaxedExp { mint append(const mint& fi) { static inv_mods<mint> invs; const int i = g.size(); if (i == 0) { assert(fi == 0); g.push_back(1); } else { g.push_back(df_g.append(i * fi, g[i - 1]) * invs[i]); } return g.back(); } mint operator[](int i) const { return g[i]; } private: std::vector<mint> g; RelaxedConvolutionNTT<mint> df_g; }; template <typename mint> struct RelaxedLog { mint append(const mint& fi) { static inv_mods<mint> invs; f.push_back(fi); const int i = g.size(); if (i == 0) { assert(f[i] == 1); g.push_back(0); } else if (i == 1) { g.push_back(f[i]); } else { g.push_back(f[i] - fg.append((i - 1) * g[i - 1], f[i - 1]) * invs[i]); } return g.back(); } mint operator[](int i) const { return g[i]; } private: std::vector<mint> f, g; RelaxedConvolutionNTT<mint> fg; }; template <typename mint> struct RelaxedPow { RelaxedPow(long long k = 0) : k(k) {} mint append(const mint& fi) { if (k == 0) { return g.emplace_back(g.empty() ? 1 : 0); } static inv_mods<mint> invs; if (is_zero) { if (fi == 0) { z = std::min(z + k, 1000000000LL); } else { is_zero = false; inv_base = fi.inv(); } } if (not is_zero) { f.push_back(fi); } if (index < z) { g.push_back(0); } else if (index == z) { g.push_back(f[0].pow(k)); } else { int i = index - z; mint v1 = fg1.append(mint(k - (i - 1)) * g[z + i - 1], f[i]); mint v2 = fg2.append(g[z + i - 1], mint(k) * (i - 1) * f[i]); g.push_back((v1 + v2) * inv_base * invs[i]); } ++index; return g.back(); } mint operator[](int i) const { return g[i]; } private: long long k; long long z = 0; long long index = 0; bool is_zero = true; mint inv_base = 0; std::vector<mint> f, g; RelaxedConvolutionNTT<mint> fg1; RelaxedConvolutionNTT<mint> fg2; }; template <typename mint> struct RelaxedSqrt { std::optional<mint> append(const mint& fi) { if (g.empty()) { auto opt_g0 = safe_sqrt(fi); if (not opt_g0) return std::nullopt; mint g0 = *opt_g0; c = (2 * g0).inv(); return g.emplace_back(g0); } else if (g.size() == 1) { return g.emplace_back(c * fi); } else { mint gi = c * (fi - gg.append(g.back(), g.back())); return g.emplace_back(gi); } } mint operator[](int i) const { return g[i]; } private: mint c = 0; std::vector<mint> g; RelaxedConvolutionNTT<mint> gg; }; } // namespace suisen #line 6 "test/src/polynomial/formal_power_series_relaxed/inv_of_formal_power_series.test.cpp" using mint = atcoder::modint998244353; std::istream& operator>>(std::istream& in, mint &a) { long long e; in >> e; a = e; return in; } std::ostream& operator<<(std::ostream& out, const mint &a) { out << a.val(); return out; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; std::cin >> n; suisen::RelaxedInv<mint> inv_f; for (int i = 0; i < n; ++i) { mint v; std::cin >> v; std::cout << inv_f.append(v) << " \n"[i == n - 1]; } }