binomial.hpp

• View this file on GitHub
• Last update: 2025-01-19 15:28:01+08:00
• Include: #include "binomial.hpp"

Required by

• basis.hpp
• C-Finite Sequence (c_finite.hpp)
• Chirp Z Transform (czt.hpp)
• falling_factorial_poly.hpp
• famous_sequence.hpp
• FPS as Linear Operator (fps_as_operator.hpp)
• fps_basic.hpp
• Formal Power Series Composition (fps_composition.hpp)
• fps_polya.hpp
• fps_sqrt.hpp
• frobenius.hpp
• mat_basic.hpp
• mat_extra.hpp
• mat_sparse.hpp
• Multivariate Power Series (mps_basic.hpp)
• poly.hpp
• poly_basic.hpp
• Polynomial Interpolation (Lagrange Interpolation) (poly_interpolation.hpp)
• poly_interpolation_with_error.hpp
• Shift Sample Points (shift_sample_points.hpp)
• Subproduct Tree (subproduct_tree.hpp)

Verified with

• test/enumerative_combinatorics/bell_number.0.test.cpp
• test/enumerative_combinatorics/factorial.0.test.cpp
• test/enumerative_combinatorics/partition_function.0.test.cpp
• test/enumerative_combinatorics/sharp_p_subset_sum.0.test.cpp
• test/enumerative_combinatorics/stirling_number_of_the_first_kind.0.test.cpp
• test/enumerative_combinatorics/stirling_number_of_the_first_kind_fixed_k.0.test.cpp
• test/enumerative_combinatorics/stirling_number_of_the_second_kind.0.test.cpp
• test/enumerative_combinatorics/stirling_number_of_the_second_kind_fixed_k.0.test.cpp
• test/formal_power_series/composition_of_formal_power_series_large.0.test.cpp
• test/formal_power_series/compositional_inverse_of_formal_power_series_large.0.test.cpp
• test/formal_power_series/consecutive_terms_of_linear_recurrent_sequence.0.test.cpp
• test/formal_power_series/conversion_from_monomial_basis_to_newton_basis.0.test.cpp
• test/formal_power_series/division_of_polynomials.0.test.cpp
• test/formal_power_series/exp_of_formal_power_series.0.test.cpp
• test/formal_power_series/find_linear_recurrence.0.test.cpp
• test/formal_power_series/inv_of_formal_power_series.0.test.cpp
• test/formal_power_series/inv_of_polynomials.0.test.cpp
• test/formal_power_series/kth_term_of_linearly_recurrent_sequence.0.test.cpp
• test/formal_power_series/log_of_formal_power_series.0.test.cpp
• test/formal_power_series/multipoint_evaluation.0.test.cpp
• test/formal_power_series/multipoint_evaluation_on_geometric_sequence.0.test.cpp
• test/formal_power_series/multivariate_power_series.0.test.cpp
• test/formal_power_series/polynomial_interpolation.0.test.cpp
• test/formal_power_series/polynomial_interpolation_on_geometric_sequence.0.test.cpp
• test/formal_power_series/polynomial_taylor_shift.0.test.cpp
• test/formal_power_series/polynomial_taylor_shift.1.test.cpp
• test/formal_power_series/pow_of_formal_power_series.0.test.cpp
• test/formal_power_series/shift_of_sampling_points_of_polynomial.0.test.cpp
• test/formal_power_series/shift_of_sampling_points_of_polynomial.1.test.cpp
• test/formal_power_series/sqrt_of_formal_power_series.0.test.cpp
• test/matrix/adjugate_matrix.0.test.cpp
• test/matrix/characteristic_polynomial.0.test.cpp
• test/matrix/characteristic_polynomial.1.test.cpp
• test/matrix/inverse_matrix.0.test.cpp
• test/matrix/matrix_det.0.test.cpp
• test/matrix/matrix_product.0.test.cpp
• test/matrix/pow_of_matrix.0.test.cpp
• test/matrix/sparse_matrix_det.0.test.cpp

Code

#pragma once

#include <algorithm>
#include <vector>

template<typename Tp> class Binomial {
    std::vector<Tp> factorial_, invfactorial_;

    Binomial() : factorial_{Tp(1)}, invfactorial_{Tp(1)} {}

    void preprocess(int n) {
        if (const int nn = factorial_.size(); nn < n) {
            int k = nn;
            while (k < n) k *= 2;
            k = std::min<long long>(k, Tp::mod());
            factorial_.resize(k);
            invfactorial_.resize(k);
            for (int i = nn; i < k; ++i) factorial_[i] = factorial_[i - 1] * i;
            invfactorial_.back() = factorial_.back().inv();
            for (int i = k - 2; i >= nn; --i) invfactorial_[i] = invfactorial_[i + 1] * (i + 1);
        }
    }

public:
    static const Binomial &get(int n) {
        static Binomial bin;
        bin.preprocess(n);
        return bin;
    }

    Tp binom(int n, int m) const {
        return n < m ? Tp() : factorial_[n] * invfactorial_[m] * invfactorial_[n - m];
    }
    Tp inv(int n) const { return factorial_[n - 1] * invfactorial_[n]; }
    Tp factorial(int n) const { return factorial_[n]; }
    Tp inv_factorial(int n) const { return invfactorial_[n]; }
};

#line 2 "binomial.hpp"

#include <algorithm>
#include <vector>

template<typename Tp> class Binomial {
    std::vector<Tp> factorial_, invfactorial_;

    Binomial() : factorial_{Tp(1)}, invfactorial_{Tp(1)} {}

    void preprocess(int n) {
        if (const int nn = factorial_.size(); nn < n) {
            int k = nn;
            while (k < n) k *= 2;
            k = std::min<long long>(k, Tp::mod());
            factorial_.resize(k);
            invfactorial_.resize(k);
            for (int i = nn; i < k; ++i) factorial_[i] = factorial_[i - 1] * i;
            invfactorial_.back() = factorial_.back().inv();
            for (int i = k - 2; i >= nn; --i) invfactorial_[i] = invfactorial_[i + 1] * (i + 1);
        }
    }

public:
    static const Binomial &get(int n) {
        static Binomial bin;
        bin.preprocess(n);
        return bin;
    }

    Tp binom(int n, int m) const {
        return n < m ? Tp() : factorial_[n] * invfactorial_[m] * invfactorial_[n - m];
    }
    Tp inv(int n) const { return factorial_[n - 1] * invfactorial_[n]; }
    Tp factorial(int n) const { return factorial_[n]; }
    Tp inv_factorial(int n) const { return invfactorial_[n]; }
};

Back to top page