Binomial
(src/math/binomial.hpp)

• View this file on GitHub
• Last update: 2024-11-09 02:03:28+09:00
• Include: #include "src/math/binomial.hpp"

Binomial

• 二項係数 $_n C _k \pmod{p}$

などを計算するアルゴリズムです．

コンストラクタ

Binomial<mint> binom(int N)

• mint の法 $p$ における $0!$ ~ $N!$ および $(0!)^{-1}$ ~ $(N!)^{-1}$ のテーブルを構築します．

制約

• $\forall_{1 \leq i \leq N} ~ \mathrm{gcd} (i, p) = 1$

計算量

• $O(N)$

fact

mint binom.fact(int n)

$n! \pmod{p}$ を返します．

$n < 0$ の場合は $0$ を返します．

制約

• $n \leq N$

計算量

• $O(1)$

perm

mint binom.perm(int n, int k)

$_n P _k \pmod{p}$ を返します．

$n < 0$ または $n < k$ または $k < 0$ の場合は $0$ を返します．

制約

• $n \leq N$

計算量

• $O(1)$

comb, operator ()

(1) mint binom.comb(int n, int k)
(2) mint binom(int n, int k)

$_n C _k \pmod{p}$ を返します．

$n < 0$ または $n < k$ または $k < 0$ の場合は $0$ を返します．

制約

• $n \leq N$

計算量

• $O(1)$

homo

mint binom.homo(int n, int k)

$_n H _k \pmod{p}$ を返します．

$n < 0$ または $k < 0$ の場合は $0$ を返します．
$k = 0$ の場合は $1$ を返します．

制約

• $n + k - 1 \leq N$

計算量

• $O(1)$

Depends on

• template (src/template/template.hpp)

Verified with

• verify/library_checker/enumerative_combinatrics/binomial_coefficient_prime_mod.test.cpp

Code

#pragma once
#include "../template/template.hpp"
template <typename mint>
struct Binomial {
    Binomial(int n)
        : fac(n + 1), ifac(n + 1) {
        fac[0] = 1;
        for(int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i;
        ifac[n] = fac[n].inv();
        for(int i = n; i >= 1; --i) ifac[i - 1] = ifac[i] * i;
    }
    mint fact(int n) const {
        if(n < 0) return 0;
        return fac[n];
    }
    mint perm(int n, int r) const {
        if(n < 0 or n < r or r < 0) return 0;
        return fac[n] * ifac[n - r];
    }
    mint comb(int n, int r) const {
        if(n < 0 or n < r or r < 0) return 0;
        return fac[n] * ifac[n - r] * ifac[r];
    }
    mint homo(int n, int r) const {
        if(n < 0 or r < 0) return 0;
        if(r == 0) return 1;
        return comb(n + r - 1, r);
    }
    mint operator()(int n, int r) const {
        return comb(n, r);
    }

   private:
    vector<mint> fac, ifac;
};

#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;
#line 3 "src/math/binomial.hpp"
template <typename mint>
struct Binomial {
    Binomial(int n)
        : fac(n + 1), ifac(n + 1) {
        fac[0] = 1;
        for(int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i;
        ifac[n] = fac[n].inv();
        for(int i = n; i >= 1; --i) ifac[i - 1] = ifac[i] * i;
    }
    mint fact(int n) const {
        if(n < 0) return 0;
        return fac[n];
    }
    mint perm(int n, int r) const {
        if(n < 0 or n < r or r < 0) return 0;
        return fac[n] * ifac[n - r];
    }
    mint comb(int n, int r) const {
        if(n < 0 or n < r or r < 0) return 0;
        return fac[n] * ifac[n - r] * ifac[r];
    }
    mint homo(int n, int r) const {
        if(n < 0 or r < 0) return 0;
        if(r == 0) return 1;
        return comb(n + r - 1, r);
    }
    mint operator()(int n, int r) const {
        return comb(n, r);
    }

   private:
    vector<mint> fac, ifac;
};

Back to top page