Powers
(library/sequence/powers.hpp)

• View this file on GitHub
• Last update: 2022-07-10 22:02:36+09:00
• Include: #include "library/sequence/powers.hpp"

Powers

Depends on

• 線形篩 (library/number/linear_sieve.hpp)

Required by

• $\displaystyle \sum _ i i ^ d r ^ i$ (library/math/sum_i^d_r^i.hpp)
• Eulerian Number (library/sequence/eulerian_number.hpp)
• Stirling Number2 (library/sequence/stirling_number2.hpp)
• Stirling Number2 Small Prime Mod (library/sequence/stirling_number2_small_prime_mod.hpp)

Verified with

• 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/lagrange_interpolation/cumulative_sum.test.cpp
• test/src/sequence/eulerian_number/yuki2005-2-2.test.cpp
• test/src/sequence/eulerian_number/yuki2005-2.test.cpp
• test/src/sequence/eulerian_number/yuki2005.test.cpp
• test/src/sequence/stirling_number2/stirling_number2.test.cpp
• test/src/sequence/stirling_number2/stirling_number2_2.test.cpp
• test/src/sequence/stirling_number2_small_prime_mod/stirling_number_of_the_second_kind_small_p_large_n.test.cpp

Code

#ifndef SUISEN_POWERS
#define SUISEN_POWERS

#include <cstdint>
#include "library/number/linear_sieve.hpp"

namespace suisen {
    // returns { 0^k, 1^k, ..., n^k }
    template <typename mint>
    std::vector<mint> powers(uint32_t n, uint64_t k) {
        const auto mpf = LinearSieve(n).get_min_prime_factor();
        std::vector<mint> res(n + 1);
        res[0] = k == 0;
        for (uint32_t i = 1; i <= n; ++i) res[i] = i == 1 ? 1 : uint32_t(mpf[i]) == i ? mint(i).pow(k) : res[mpf[i]] * res[i / mpf[i]];
        return res;
    }
} // namespace suisen

#endif // SUISEN_POWERS

#line 1 "library/sequence/powers.hpp"



#include <cstdint>
#line 1 "library/number/linear_sieve.hpp"



#include <cassert>
#include <numeric>
#include <vector>

namespace suisen {
// referece: https://37zigen.com/linear-sieve/
class LinearSieve {
    public:
        LinearSieve(const int n) : _n(n), min_prime_factor(std::vector<int>(n + 1)) {
            std::iota(min_prime_factor.begin(), min_prime_factor.end(), 0);
            prime_list.reserve(_n / 20);
            for (int d = 2; d <= _n; ++d) {
                if (min_prime_factor[d] == d) prime_list.push_back(d);
                const int prime_max = std::min(min_prime_factor[d], _n / d);
                for (int prime : prime_list) {
                    if (prime > prime_max) break;
                    min_prime_factor[prime * d] = prime;
                }
            }
        }
        int prime_num() const noexcept { return prime_list.size(); }
        /**
         * Returns a vector of primes in [0, n].
         * It is guaranteed that the returned vector is sorted in ascending order.
         */
        const std::vector<int>& get_prime_list() const noexcept  {
            return prime_list;
        }
        const std::vector<int>& get_min_prime_factor() const noexcept { return min_prime_factor; }
        /**
         * Returns a vector of `{ prime, index }`.
         * It is guaranteed that the returned vector is sorted in ascending order.
         */
        std::vector<std::pair<int, int>> factorize(int n) const noexcept {
            assert(0 < n and n <= _n);
            std::vector<std::pair<int, int>> prime_powers;
            while (n > 1) {
                int p = min_prime_factor[n], c = 0;
                do { n /= p, ++c; } while (n % p == 0);
                prime_powers.emplace_back(p, c);
            }
            return prime_powers;
        }
    private:
        const int _n;
        std::vector<int> min_prime_factor;
        std::vector<int> prime_list;
};
} // namespace suisen


#line 6 "library/sequence/powers.hpp"

namespace suisen {
    // returns { 0^k, 1^k, ..., n^k }
    template <typename mint>
    std::vector<mint> powers(uint32_t n, uint64_t k) {
        const auto mpf = LinearSieve(n).get_min_prime_factor();
        std::vector<mint> res(n + 1);
        res[0] = k == 0;
        for (uint32_t i = 1; i <= n; ++i) res[i] = i == 1 ? 1 : uint32_t(mpf[i]) == i ? mint(i).pow(k) : res[mpf[i]] * res[i / mpf[i]];
        return res;
    }
} // namespace suisen

Back to top page