Binomial Coefficients
(src/math/binomial.hpp)

• View this file on GitHub
• Last update: 2024-10-28 15:43:27+09:00
• Include: #include "src/math/binomial.hpp"

概要

$\mathbb{Z}/p\mathbb{Z}$ における二項係数を扱うライブラリ． $n$ の上限等を指定する必要はなく，不十分な場合に適宜上限を $2$ 倍にしていくことで効率的に計算する． 上限 $n$，クエリ数 $q$ の際の時間計算量は $\mathrm{O}(q + n + \log n\log p)$，空間計算量は $\mathrm{O}(n)$ となる．

下記の時間計算量については構築にかかる時間計算量は含んでいない．

メンバ関数	効果	時間計算量
fac(i)	$i!$ を返す．	$\mathrm{O}(1)$
finv(i)	$\frac{1}{i!}$ を返す．	$\mathrm{O}(1)$
inv(i)	$\frac{1}{i}$ を返す．	$\mathrm{O}(1)$
P(n, r)	${}_n\mathrm{P}_r = \frac{n!}{r!}$ を返す．	$\mathrm{O}(1)$
C(n, r)	${}_n \mathrm{C}_r = \binom{n}{r} = \frac{n!}{(n - r)!r!}$ を返す．	$\mathrm{O}(1)$
H(n, r)	${}_n \mathrm{H}_r = \binom{n + r - 1}{r}$，すなわち $n$ 種類のものから重複を許して $r$ 個取り出す組み合わせの総数を返す．	$\mathrm{O}(1)$
negative_binom(n, k)	$\lbrack x ^ n \rbrack \frac{1}{(1 - x) ^ k}$ を返す．	$\mathrm{O}(1)$
C_naive(n, r)	$\binom{n}{r}$ を愚直に計算する．	$\mathrm{O}(\min(r, n - r))$
catalan(n)	$n$ 番目の Catalan 数を返す．	$\mathrm{O}(1)$
catalan1(n, m)	$+1$ が $n$ 個，$-1$ が $m$ 個からなる数列であって，累積和がどれも $0$ 以上であるようなものの個数を返す．	$\mathrm{O}(1)$
catalan2(n, m, k)	$+1$ が $n$ 個，$-1$ が $m$ 個からなる数列であって，累積和がどれも $- k$ より大きいようなものの個数を返す．	$\mathrm{O}(1)$
catalan_pow(n, k)	Catalan 数の母関数を $C(x)$ として，$\lbrack x ^ n \rbrack C ^ k (x)$ を返す．	$\mathrm{O}(1)$
narayana(n, k)	Narayana 数 $N(n, k)$ を返す．これは長さ $2 n$ の括弧列であって，連続部分列として () を丁度 $k$ 個含むようなものの個数に等しい．	$\mathrm{O}(1)$
grid_sum(x, y)	$\sum _ {i = 0} ^ x \sum _ {j = 0} ^ y \binom{i + j}{i}$ を返す．	$\mathrm{O}(1)$
grid_sum2(xl, xr, yl, yr)	$\sum _ {i = x _ l} ^ {x _ r - 1} \sum _ {j = y _ l} ^ {y _ r - 1} \binom{i + j}{i}$ を返す．	$\mathrm{O}(1)$

Required by

• Bell Number (src/enumerative_combinatorics/bell_number.hpp)
• Number of Increasing Sequences Between Two Sequences (src/math/number_of_increasing_sequences_between_two_sequences.hpp)
• Lagrange Interpolation (src/polynomial/lagrange_interpolation.hpp)

Verified with

• test/aoj/DPL_5_E.test.cpp
• test/yosupo/bell_number.test.cpp
• test/yosupo/binomial_coefficient_prime_mod.test.cpp
• test/yosupo/number_of_increasing_sequences_between_two_sequences.test.cpp
• test/yukicoder/665.test.cpp

Code

#pragma once
#include <algorithm>
#include <cassert>
#include <vector>

template <typename T> struct Binomial {
    Binomial(int MAX = 0) : n(1), facs(1, T(1)), finvs(1, T(1)), invs(1, T(1)) {
        assert(T::mod() != 0);
        if (MAX > 0) extend(MAX + 1);
    }

    T fac(int i) {
        assert(i >= 0);
        while (n <= i) extend();
        return facs[i];
    }

    T finv(int i) {
        assert(i >= 0);
        while (n <= i) extend();
        return finvs[i];
    }

    T inv(int i) {
        assert(i >= 0);
        while (n <= i) extend();
        return invs[i];
    }

    T P(int n, int r) {
        if (n < r or r < 0) return 0;
        return fac(n) * finv(n - r);
    }

    T C(int n, int r) {
        if (n < r or r < 0) return 0;
        return fac(n) * finv(n - r) * finv(r);
    }

    T H(int n, int r) {
        if (n < 0 or r < 0) return 0;
        return r == 0 ? 1 : C(n + r - 1, r);
    }

    T negative_binom(int n, int k) { return H(k, n); }

    T C_naive(int n, int r) {
        if (n < r or r < 0) return 0;
        T res = 1;
        r = std::min(r, n - r);
        for (int i = 1; i <= r; i++) res *= inv(i) * (n--);
        return res;
    }

    T catalan(int n) {
        if (n < 0) return 0;
        return fac(2 * n) * finv(n + 1) * finv(n);
    }

    T catalan_pow(int n, int k) {
        if (n < 0 or k < 0) return 0;
        if (k == 0) return n == 0 ? 1 : 0;
        return inv(n + k) * k * C(2 * n + k - 1, n);
    }

    T calatan1(int n, int m) { return C(n + m, m) - C(n + m, m - 1); }

    T catalan2(int n, int m, int k) { return n - m <= -k ? 0 : C(n + m, m) - C(n + m, m - k); }

    T narayana(int n, int k) {
        if (n < k or k <= 0) return 0;
        return C(n, k) * C(n, k - 1) * inv(n);
    }

    T grid_sum(int x, int y) {
        if (x < 0 or y < 0) return 0;
        return C(x + y + 2, x + 1) - 1;
    }

    T grid_sum2(int xl, int xr, int yl, int yr) {
        if (xl >= xr or yl >= yr) return 0;
        xl--, xr--, yl--, yr--;
        return grid_sum(xr, yr) - grid_sum(xl, yr) - grid_sum(xr, yl) + grid_sum(xl, yl);
    }

  private:
    int n;
    std::vector<T> facs, finvs, invs;

    inline void extend(int m = -1) {
        if (m == -1) m = n * 2;
        m = std::min(m, T::mod());
        if (n >= m) return;
        facs.resize(m);
        finvs.resize(m);
        invs.resize(m);
        for (int i = n; i < m; i++) facs[i] = facs[i - 1] * i;
        finvs[m - 1] = T(1) / facs[m - 1];
        invs[m - 1] = finvs[m - 1] * facs[m - 2];
        for (int i = m - 2; i >= n; i--) {
            finvs[i] = finvs[i + 1] * (i + 1);
            invs[i] = finvs[i] * facs[i - 1];
        }
        n = m;
    }
};

#line 2 "src/math/binomial.hpp"
#include <algorithm>
#include <cassert>
#include <vector>

template <typename T> struct Binomial {
    Binomial(int MAX = 0) : n(1), facs(1, T(1)), finvs(1, T(1)), invs(1, T(1)) {
        assert(T::mod() != 0);
        if (MAX > 0) extend(MAX + 1);
    }

    T fac(int i) {
        assert(i >= 0);
        while (n <= i) extend();
        return facs[i];
    }

    T finv(int i) {
        assert(i >= 0);
        while (n <= i) extend();
        return finvs[i];
    }

    T inv(int i) {
        assert(i >= 0);
        while (n <= i) extend();
        return invs[i];
    }

    T P(int n, int r) {
        if (n < r or r < 0) return 0;
        return fac(n) * finv(n - r);
    }

    T C(int n, int r) {
        if (n < r or r < 0) return 0;
        return fac(n) * finv(n - r) * finv(r);
    }

    T H(int n, int r) {
        if (n < 0 or r < 0) return 0;
        return r == 0 ? 1 : C(n + r - 1, r);
    }

    T negative_binom(int n, int k) { return H(k, n); }

    T C_naive(int n, int r) {
        if (n < r or r < 0) return 0;
        T res = 1;
        r = std::min(r, n - r);
        for (int i = 1; i <= r; i++) res *= inv(i) * (n--);
        return res;
    }

    T catalan(int n) {
        if (n < 0) return 0;
        return fac(2 * n) * finv(n + 1) * finv(n);
    }

    T catalan_pow(int n, int k) {
        if (n < 0 or k < 0) return 0;
        if (k == 0) return n == 0 ? 1 : 0;
        return inv(n + k) * k * C(2 * n + k - 1, n);
    }

    T calatan1(int n, int m) { return C(n + m, m) - C(n + m, m - 1); }

    T catalan2(int n, int m, int k) { return n - m <= -k ? 0 : C(n + m, m) - C(n + m, m - k); }

    T narayana(int n, int k) {
        if (n < k or k <= 0) return 0;
        return C(n, k) * C(n, k - 1) * inv(n);
    }

    T grid_sum(int x, int y) {
        if (x < 0 or y < 0) return 0;
        return C(x + y + 2, x + 1) - 1;
    }

    T grid_sum2(int xl, int xr, int yl, int yr) {
        if (xl >= xr or yl >= yr) return 0;
        xl--, xr--, yl--, yr--;
        return grid_sum(xr, yr) - grid_sum(xl, yr) - grid_sum(xr, yl) + grid_sum(xl, yl);
    }

  private:
    int n;
    std::vector<T> facs, finvs, invs;

    inline void extend(int m = -1) {
        if (m == -1) m = n * 2;
        m = std::min(m, T::mod());
        if (n >= m) return;
        facs.resize(m);
        finvs.resize(m);
        invs.resize(m);
        for (int i = n; i < m; i++) facs[i] = facs[i - 1] * i;
        finvs[m - 1] = T(1) / facs[m - 1];
        invs[m - 1] = finvs[m - 1] * facs[m - 2];
        for (int i = m - 2; i >= n; i--) {
            finvs[i] = finvs[i + 1] * (i + 1);
            invs[i] = finvs[i] * facs[i - 1];
        }
        n = m;
    }
};

Back to top page