math/pow_table.hpp

• View this file on GitHub
• Last update: 2022-09-10 18:25:53+09:00
• Include: #include "math/pow_table.hpp"

Required by

• Range Update Range Hash (string/range_update_range_hash.hpp)
• Rolling Hash (string/rolling_hash.hpp)

Verified with

• test/aoj/0355.test.cpp
• test/library-checker/enumerate_palindromes.test.cpp
• test/library-checker/suffix_array_rolling_hash.test.cpp
• test/library-checker/zalgorithm_rolling_hash.test.cpp
• test/yukicoder/2231.test.cpp

Code

#pragma once
#include <vector>
template <typename mint>
struct pow_mods {
    pow_mods() {
    }
    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;
};

#line 2 "math/pow_table.hpp"
#include <vector>
template <typename mint>
struct pow_mods {
    pow_mods() {
    }
    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