cp-library-cpp

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub suisen-cp/cp-library-cpp

:warning: Binomial Coefficitnt Enumeration
(library/sequence/binomial_coefficitnt_enumeration.hpp)

Binomial Coefficitnt Enumeration

Depends on

Code

#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
Back to top page