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/exp_of_formal_power_series" #include <iostream> #include <atcoder/modint> #include "library/math/inv_mods.hpp" #include "library/convolution/semi_relaxed_convolution_ntt.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; } namespace suisen { template <typename mint> std::vector<mint> exp(const std::vector<mint>& f) { inv_mods<mint> invs; const int n = f.size(); std::vector<mint> df(n - 1); for (int i = 1; i < n; ++i) { df[i - 1] = i * f[i]; } SemiRelaxedConvolutionNTT<mint> df_g(df); std::vector<mint> g(n); g[0] = 1; for (int i = 1; i < n; ++i) { g[i] = df_g.append(g[i - 1]) * invs[i]; } return g; } } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; std::cin >> n; std::vector<mint> f(n); for (auto &e : f) std::cin >> e; std::vector<mint> exp_f = suisen::exp(f); for (int i = 0; i < n; ++i) { std::cout << exp_f[i] << " \n"[i == n - 1]; } }
#line 1 "test/src/convolution/semi_relaxed_convolution_ntt/exp_of_formal_power_series.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/exp_of_formal_power_series" #include <iostream> #include <atcoder/modint> #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/semi_relaxed_convolution_ntt.hpp" #include <atcoder/convolution> namespace suisen { // reference: https://qiita.com/Kiri8128/items/1738d5403764a0e26b4c template <typename mint> struct SemiRelaxedConvolutionNTT { SemiRelaxedConvolutionNTT() = default; SemiRelaxedConvolutionNTT(const std::vector<mint> &f) : _n(0), _f(f), _g{}, _h{} {} mint append(const mint& gi) { static constexpr int threshold_log = 6; static constexpr int threshold = 1 << threshold_log; static constexpr int threshold_mask = threshold - 1; ++_n; _g.push_back(gi); int q = _n >> threshold_log, r = _n & threshold_mask; if (r == 0) { if (q == (-q & q)) { std::vector<mint> f_fft(_f.begin(), _f.begin() + std::min(int(_f.size()), 2 * _n)); f_fft.resize(2 * _n); atcoder::internal::butterfly(f_fft); _f_fft.push_back(std::move(f_fft)); } const int log_q = __builtin_ctz(q); const int k = (-q & q) << threshold_log; std::vector<mint> g_fft(_g.end() - k, _g.end()); g_fft.resize(2 * k); atcoder::internal::butterfly(g_fft); const mint z = mint(2 * k).inv(); std::vector<mint> h(2 * k); for (int i = 0; i < 2 * k; ++i) h[i] = _f_fft[log_q][i] * g_fft[i] * z; atcoder::internal::butterfly_inv(h); ensure(_n - 1 + k); for (int i = 0; i < k; ++i) _h[_n - 1 + i] += h[k - 1 + i]; } else { // naive convolve r = std::min(r, int(_f.size())); ensure(_n); for (int i = 0; i < r; ++i) { _h[_n - 1] += _f[i] * _g[_n - 1 - 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; void ensure(std::size_t n) { if (_h.size() < n) _h.resize(n); } }; } // namespace suisen #line 8 "test/src/convolution/semi_relaxed_convolution_ntt/exp_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; } namespace suisen { template <typename mint> std::vector<mint> exp(const std::vector<mint>& f) { inv_mods<mint> invs; const int n = f.size(); std::vector<mint> df(n - 1); for (int i = 1; i < n; ++i) { df[i - 1] = i * f[i]; } SemiRelaxedConvolutionNTT<mint> df_g(df); std::vector<mint> g(n); g[0] = 1; for (int i = 1; i < n; ++i) { g[i] = df_g.append(g[i - 1]) * invs[i]; } return g; } } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; std::cin >> n; std::vector<mint> f(n); for (auto &e : f) std::cin >> e; std::vector<mint> exp_f = suisen::exp(f); for (int i = 0; i < n; ++i) { std::cout << exp_f[i] << " \n"[i == n - 1]; } }