math/pow_sum_table.hpp

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

Required by

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

Verified with

• test/aoj/0355.test.cpp

Code

#pragma once
template <typename mint>
struct pow_mod_sums {
    pow_mod_sums() {
    }
    pow_mod_sums(mint base, int n) : base(base) {
        ensure(n);
    }
    // sum(pow[0..i])
    const mint& operator[](int i) const {
        ensure(i);
        return pow_sums[i];
    }
    void ensure(int n) const {
        int sz = pow_sums.size();
        if (sz > n) return;
        pow_sums.resize(n + 1);
        pows.resize(n + 1);
        for (int i = sz; i <= n; i++) {
            pows[i] = base * pows[i - 1];
            pow_sums[i] = pow_sums[i - 1] + pows[i - 1];
        }
    }

private:
    mutable std::vector<mint> pow_sums{0};
    mutable std::vector<mint> pows{1};
    mint base;
    static constexpr int mod = mint::mod;
};

#line 2 "math/pow_sum_table.hpp"
template <typename mint>
struct pow_mod_sums {
    pow_mod_sums() {
    }
    pow_mod_sums(mint base, int n) : base(base) {
        ensure(n);
    }
    // sum(pow[0..i])
    const mint& operator[](int i) const {
        ensure(i);
        return pow_sums[i];
    }
    void ensure(int n) const {
        int sz = pow_sums.size();
        if (sz > n) return;
        pow_sums.resize(n + 1);
        pows.resize(n + 1);
        for (int i = sz; i <= n; i++) {
            pows[i] = base * pows[i - 1];
            pow_sums[i] = pow_sums[i - 1] + pows[i - 1];
        }
    }

private:
    mutable std::vector<mint> pow_sums{0};
    mutable std::vector<mint> pows{1};
    mint base;
    static constexpr int mod = mint::mod;
};

Back to top page