This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#include "library/sequence/binomial_coefficitnt_enumeration.hpp"
#ifndef SUISEN_ANY_MOD_BINOM #define SUISEN_ANY_MOD_BINOM #include "library/number/linear_sieve.hpp" namespace suisen { /** * calc Binom[N, k] mod M for all k = 0, ..., N in O(NlogM/loglogM) time. * * reference: https://qiita.com/suisen_cp/items/d0ab7e728b98bbec818f */ template <typename mint> class ArbitraryModBinomialCoefficients { public: ArbitraryModBinomialCoefficients(const unsigned int N): _N(N), _M(mint::mod()), _sieve(N), _binom(N + 1) { solve(); } inline mint operator[](const unsigned int k) const { return _binom[k]; } const std::vector<mint>& get_coeffs() const { return _binom; } const LinearSieve& get_sieve() const { return _sieve; } private: const unsigned int _N, _M; const LinearSieve _sieve; std::vector<mint> _binom; std::vector<mint> mod_invs() const { std::vector<mint> invs(_N + 1); const auto& mpf = _sieve.get_min_prime_factor(); if (_N >= 1) invs[1] = 1; for (unsigned int i = 2; i <= _N; ++i) { const unsigned int pf = mpf[i]; if (pf == i) { if (_M % pf) invs[i] = mint(i).inv(); } else { invs[i] = invs[pf] * invs[i / pf]; } } return invs; } std::vector<std::vector<mint>> precalc_powers(const unsigned int L, const std::vector<unsigned int>& primes) const { std::vector<std::vector<mint>> powers(L + 1); for (unsigned int i = 1; i <= L; ++i) { const unsigned int max_index = _N / (primes[i] - 1); powers[i].resize(max_index + 1); const mint pi = primes[i]; powers[i][0] = 1; for (unsigned int j = 0; j < max_index; ++j) { powers[i][j + 1] = powers[i][j] * pi; } } return powers; } void solve() { auto& primes = _sieve.get_prime_list(); std::vector<unsigned int> divisor_index(_N + 1, 0); std::vector<unsigned int> p; for (unsigned int prime : primes) { if (_M % prime) continue; p.push_back(prime); const unsigned int sz = p.size(); for (unsigned int v = prime; v <= _N; v += prime) divisor_index[v] = sz; } const unsigned int L = p.size(); p.insert(p.begin(), 0); std::vector<mint> invs = mod_invs(); std::vector<std::vector<mint>> powers = precalc_powers(L, p); const unsigned int half = (_N + 1) / 2; mint S = 1; std::vector<unsigned int> T(L + 1, 0); _binom[0] = 1; for (unsigned int k = 1; k <= half; ++k) { unsigned int num = _N - k + 1, den = k; while (divisor_index[num]) ++T[divisor_index[num]], num /= p[divisor_index[num]]; while (divisor_index[den]) --T[divisor_index[den]], den /= p[divisor_index[den]]; S *= num * invs[den]; _binom[k] = S; for (unsigned int i = 1; i <= L; ++i) _binom[k] *= powers[i][T[i]]; } for (unsigned int k = half + 1; k <= _N; ++k) _binom[k] = _binom[_N - k]; } }; } // namespace suisen #endif // SUISEN_ANY_MOD_BINOM
#line 1 "library/sequence/binomial_coefficitnt_enumeration.hpp" #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 5 "library/sequence/binomial_coefficitnt_enumeration.hpp" namespace suisen { /** * calc Binom[N, k] mod M for all k = 0, ..., N in O(NlogM/loglogM) time. * * reference: https://qiita.com/suisen_cp/items/d0ab7e728b98bbec818f */ template <typename mint> class ArbitraryModBinomialCoefficients { public: ArbitraryModBinomialCoefficients(const unsigned int N): _N(N), _M(mint::mod()), _sieve(N), _binom(N + 1) { solve(); } inline mint operator[](const unsigned int k) const { return _binom[k]; } const std::vector<mint>& get_coeffs() const { return _binom; } const LinearSieve& get_sieve() const { return _sieve; } private: const unsigned int _N, _M; const LinearSieve _sieve; std::vector<mint> _binom; std::vector<mint> mod_invs() const { std::vector<mint> invs(_N + 1); const auto& mpf = _sieve.get_min_prime_factor(); if (_N >= 1) invs[1] = 1; for (unsigned int i = 2; i <= _N; ++i) { const unsigned int pf = mpf[i]; if (pf == i) { if (_M % pf) invs[i] = mint(i).inv(); } else { invs[i] = invs[pf] * invs[i / pf]; } } return invs; } std::vector<std::vector<mint>> precalc_powers(const unsigned int L, const std::vector<unsigned int>& primes) const { std::vector<std::vector<mint>> powers(L + 1); for (unsigned int i = 1; i <= L; ++i) { const unsigned int max_index = _N / (primes[i] - 1); powers[i].resize(max_index + 1); const mint pi = primes[i]; powers[i][0] = 1; for (unsigned int j = 0; j < max_index; ++j) { powers[i][j + 1] = powers[i][j] * pi; } } return powers; } void solve() { auto& primes = _sieve.get_prime_list(); std::vector<unsigned int> divisor_index(_N + 1, 0); std::vector<unsigned int> p; for (unsigned int prime : primes) { if (_M % prime) continue; p.push_back(prime); const unsigned int sz = p.size(); for (unsigned int v = prime; v <= _N; v += prime) divisor_index[v] = sz; } const unsigned int L = p.size(); p.insert(p.begin(), 0); std::vector<mint> invs = mod_invs(); std::vector<std::vector<mint>> powers = precalc_powers(L, p); const unsigned int half = (_N + 1) / 2; mint S = 1; std::vector<unsigned int> T(L + 1, 0); _binom[0] = 1; for (unsigned int k = 1; k <= half; ++k) { unsigned int num = _N - k + 1, den = k; while (divisor_index[num]) ++T[divisor_index[num]], num /= p[divisor_index[num]]; while (divisor_index[den]) --T[divisor_index[den]], den /= p[divisor_index[den]]; S *= num * invs[den]; _binom[k] = S; for (unsigned int i = 1; i <= L; ++i) _binom[k] *= powers[i][T[i]]; } for (unsigned int k = half + 1; k <= _N; ++k) _binom[k] = _binom[_N - k]; } }; } // namespace suisen