冪乗テーブル
(library/math/pow_mods.hpp)

• View this file on GitHub
• Last update: 2023-07-09 04:04:16+09:00
• Include: #include "library/math/pow_mods.hpp"

冪乗テーブル

Required by

• Binomial Coefficient Sum (library/math/binomial_coefficient_sum.hpp)
• $\displaystyle \sum _ i i ^ d r ^ i$ (library/math/sum_i^d_r^i.hpp)
• $\left(\prod_{k=0}^{m-1} f(r^k x)\right) \bmod x^N$ (library/polynomial/prod_f(r^k_x).hpp)
• library/sequence/sum_of_powers.hpp
• Rolling Hash (library/string/rolling_hash.hpp)

Verified with

• test/src/math/binomial_coefficient_sum/yuki2512.test.cpp
• test/src/math/sum_i^d_r^i/sum_of_exponential_times_polynomial.test.cpp
• test/src/math/sum_i^d_r^i/sum_of_exponential_times_polynomial_limit.test.cpp
• test/src/polynomial/compose_exp/arc154_f.test.cpp
• test/src/polynomial/prod_f(r^k_x)/yuki2097.test.cpp
• test/src/string/rolling_hash/abc141_e.test.cpp

Code

#ifndef SUISEN_POW_MOD
#define SUISEN_POW_MOD

#include <vector>

namespace suisen {
    template <int base_as_int, typename mint>
    struct static_pow_mods {
        static_pow_mods() = default;
        static_pow_mods(int n) { ensure(n); }
        const mint& operator[](int i) const {
            ensure(i);
            return pows[i];
        }
        static void ensure(int n) {
            int sz = pows.size();
            if (sz > n) return;
            pows.resize(n + 1);
            for (int i = sz; i <= n; ++i) pows[i] = base * pows[i - 1];
        }
    private:
        static inline std::vector<mint> pows { 1 };
        static inline mint base = base_as_int;
        static constexpr int mod = mint::mod();
    };

    template <typename mint>
    struct pow_mods {
        pow_mods() = default;
        pow_mods(mint base, int n) : base(base) { ensure(n); }
        const mint& operator[](int i) const {
            ensure(i);
            return pows[i];
        }
        void ensure(int n) const {
            int sz = pows.size();
            if (sz > n) return;
            pows.resize(n + 1);
            for (int i = sz; i <= n; ++i) pows[i] = base * pows[i - 1];
        }
    private:
        mutable std::vector<mint> pows { 1 };
        mint base;
        static constexpr int mod = mint::mod();
    };
}

#endif // SUISEN_POW_MOD

#line 1 "library/math/pow_mods.hpp"



#include <vector>

namespace suisen {
    template <int base_as_int, typename mint>
    struct static_pow_mods {
        static_pow_mods() = default;
        static_pow_mods(int n) { ensure(n); }
        const mint& operator[](int i) const {
            ensure(i);
            return pows[i];
        }
        static void ensure(int n) {
            int sz = pows.size();
            if (sz > n) return;
            pows.resize(n + 1);
            for (int i = sz; i <= n; ++i) pows[i] = base * pows[i - 1];
        }
    private:
        static inline std::vector<mint> pows { 1 };
        static inline mint base = base_as_int;
        static constexpr int mod = mint::mod();
    };

    template <typename mint>
    struct pow_mods {
        pow_mods() = default;
        pow_mods(mint base, int n) : base(base) { ensure(n); }
        const mint& operator[](int i) const {
            ensure(i);
            return pows[i];
        }
        void ensure(int n) const {
            int sz = pows.size();
            if (sz > n) return;
            pows.resize(n + 1);
            for (int i = sz; i <= n; ++i) pows[i] = base * pows[i - 1];
        }
    private:
        mutable std::vector<mint> pows { 1 };
        mint base;
        static constexpr int mod = mint::mod();
    };
}

Back to top page