math/binomial.hpp

• View this file on GitHub
• Last update: 2025-01-28 23:59:05+09:00
• Include: #include "math/binomial.hpp"

Required by

• fps/fps_ntt.hpp
• fps/sample_point_shift.hpp
• fps998244353/bostan_mori.hpp
• fps998244353/fps998244353.hpp
• fps998244353/multipoint_evaluation.hpp
• fps998244353/polynomial_taylor_shift.hpp
• fps998244353/product_1_minus_x_pow_a.hpp
• fps998244353/sample_point_shift.hpp
• math/euler_circuit_counting.hpp
• Lagrange interpolation (math/lagrange_interpolation.hpp)

Verified with

• test/fps/Inv_of_Formal_Power_Series.test.cpp
• test/fps/Multipoint_Evaluation_Geometric_Sequence.test.cpp
• test/fps/Shift_of_Sampling_Points_of_Polynomial.test.cpp
• test/fps/convolution.test.cpp
• test/fps998244353/Division_of_Polynomials_998244353.test.cpp
• test/fps998244353/Kth_term_of_Linearly_Recurrent_Sequence.test.cpp
• test/fps998244353/convolution_998244353.test.cpp
• test/fps998244353/multipoint_evaluation_998244353.test.cpp
• test/fps998244353/multipoint_evaluation_geo_998244353.test.cpp
• test/fps998244353/polynomial_taylor_shift_998244353.test.cpp
• test/fps998244353/shift_of_sampling_points_of_polynomial_998244353.test.cpp
• test/math/Binomial_Coefficient_Prime_Mod.test.cpp
• test/math/Binomial_Coefficient_Prime_Mod_modintnew.test.cpp
• test/math/CountingEulerianCircuits.test.cpp

Code

#pragma once

#include<vector>
namespace noya2 {

template<typename mint>
struct binomial {
    binomial(int len = 300000){ extend(len); }
    static mint fact(int n){
        if (n < 0) return 0;
        while (n >= (int)_fact.size()) extend();
        return _fact[n];
    }
    static mint ifact(int n){
        if (n < 0) return 0;
        while (n >= (int)_fact.size()) extend();
        return _ifact[n];
    }
    static mint inv(int n){
        return ifact(n) * fact(n-1);
    }
    static mint C(int n, int r){
        if (!(0 <= r && r <= n)) return 0;
        return fact(n) * ifact(r) * ifact(n-r);
    }
    static mint P(int n, int r){
        if (!(0 <= r && r <= n)) return 0;
        return fact(n) * ifact(n-r);
    }
    static mint catalan(int n){
        return C(n * 2, n) * inv(n + 1);
    }
    inline mint operator()(int n, int r) { return C(n, r); }
    template<class... Cnts>
    static mint M(const Cnts&... cnts){
        return multinomial(0,1,cnts...);
    }
    static void initialize(int len = 2){
        _fact.clear();
        _ifact.clear();
        extend(len);
    }
  private:
    static mint multinomial(const int& sum, const mint& div_prod){
        if (sum < 0) return 0;
        return fact(sum) * div_prod;
    }
    template<class... Tail>
    static mint multinomial(const int& sum, const mint& div_prod, const int& n1, const Tail&... tail){
        if (n1 < 0) return 0;
        return multinomial(sum+n1,div_prod*ifact(n1),tail...);
    }
    static inline std::vector<mint> _fact, _ifact;
    static void extend(int len = -1){
        if (_fact.empty()){
            _fact = _ifact = {1,1};
        }
        int siz = _fact.size();
        if (len == -1) len = siz * 2;
        len = (int)min<long long>(len, mint::mod() - 1);
        if (len < siz) return ;
        _fact.resize(len+1), _ifact.resize(len+1);
        for (int i = siz; i <= len; i++) _fact[i] = _fact[i-1] * i;
        _ifact[len] = _fact[len].inv();
        for (int i = len; i > siz; i--) _ifact[i-1] = _ifact[i] * i;
    }
};

} // namespace noya2

#line 2 "math/binomial.hpp"

#include<vector>
namespace noya2 {

template<typename mint>
struct binomial {
    binomial(int len = 300000){ extend(len); }
    static mint fact(int n){
        if (n < 0) return 0;
        while (n >= (int)_fact.size()) extend();
        return _fact[n];
    }
    static mint ifact(int n){
        if (n < 0) return 0;
        while (n >= (int)_fact.size()) extend();
        return _ifact[n];
    }
    static mint inv(int n){
        return ifact(n) * fact(n-1);
    }
    static mint C(int n, int r){
        if (!(0 <= r && r <= n)) return 0;
        return fact(n) * ifact(r) * ifact(n-r);
    }
    static mint P(int n, int r){
        if (!(0 <= r && r <= n)) return 0;
        return fact(n) * ifact(n-r);
    }
    static mint catalan(int n){
        return C(n * 2, n) * inv(n + 1);
    }
    inline mint operator()(int n, int r) { return C(n, r); }
    template<class... Cnts>
    static mint M(const Cnts&... cnts){
        return multinomial(0,1,cnts...);
    }
    static void initialize(int len = 2){
        _fact.clear();
        _ifact.clear();
        extend(len);
    }
  private:
    static mint multinomial(const int& sum, const mint& div_prod){
        if (sum < 0) return 0;
        return fact(sum) * div_prod;
    }
    template<class... Tail>
    static mint multinomial(const int& sum, const mint& div_prod, const int& n1, const Tail&... tail){
        if (n1 < 0) return 0;
        return multinomial(sum+n1,div_prod*ifact(n1),tail...);
    }
    static inline std::vector<mint> _fact, _ifact;
    static void extend(int len = -1){
        if (_fact.empty()){
            _fact = _ifact = {1,1};
        }
        int siz = _fact.size();
        if (len == -1) len = siz * 2;
        len = (int)min<long long>(len, mint::mod() - 1);
        if (len < siz) return ;
        _fact.resize(len+1), _ifact.resize(len+1);
        for (int i = siz; i <= len; i++) _fact[i] = _fact[i-1] * i;
        _ifact[len] = _fact[len].inv();
        for (int i = len; i > siz; i--) _ifact[i-1] = _ifact[i] * i;
    }
};

} // namespace noya2

Back to top page