test/src/polynomial/formal_power_series_relaxed/exp_of_formal_power_series.test.cpp

• View this file on GitHub
• Last update: 2023-07-09 04:04:16+09:00
• Problem: https://judge.yosupo.jp/problem/exp_of_formal_power_series

Depends on

• Relaxed Convolution Ntt (library/convolution/relaxed_convolution_ntt.hpp)
• 逆元テーブル (library/math/inv_mods.hpp)
• Modint Extension (library/math/modint_extension.hpp)
• Formal Power Series Relaxed (library/polynomial/formal_power_series_relaxed.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/exp_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::RelaxedExp<mint> exp_f;
    for (int i = 0; i < n; ++i) {
        mint v;
        std::cin >> v;
        std::cout << exp_f.append(v) << " \n"[i == n - 1];
    }
}

#line 1 "test/src/polynomial/formal_power_series_relaxed/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/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/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;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;
    
    suisen::RelaxedExp<mint> exp_f;
    for (int i = 0; i < n; ++i) {
        mint v;
        std::cin >> v;
        std::cout << exp_f.append(v) << " \n"[i == n - 1];
    }
}

Back to top page