二項係数 (素数 mod) (EnumerativeCombinatorics/binomial_coefficient_prime_mod.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2025-05-02 21:11:09+09:00
• Include: #include "EnumerativeCombinatorics/binomial_coefficient_prime_mod.hpp"

二項係数 (素数 mod)

二項係数 $nCk = \frac{n!}{k!(n-k)!}$ を素数 $m$ で割った余りが計算できます。

参考

• AtCoder解説放送ライブラリ集

コンストラクタ

combination<mint>(int n)

二項係数 $aCb$ を高速に計算するためのクラスです。 階乗およびその逆元を事前に前計算し、任意の $0 \leq b \leq a \leq n$ に対して定数時間で値を取得できます。 テンプレート引数 mint には、atcoder::modint 系の型を指定することを前提としています。

制約

• $0 \le n <$ mint::mod()

計算量

• : $O(n)$

メンバ関数

mint operator()(int n, int k)

二項係数 $\binom{n}{k}$ を法 $m$ で割った余りとして返します。

計算量

• $O(1)$

Verified with

• test/EnumerativeCombinatorics/binomial_coefficient_prime_mod/yosupo-binomial_coefficient_prime_mod.cpp

Code

#include <bits/stdc++.h>
using namespace std;

template <class mint>
class combination
{
private:
    vector<mint> fact, ifact;

public:
    combination(int n) : fact(n + 1), ifact(n + 1)
    {
        assert(n < mint::mod());
        fact[0] = 1;
        for (int i = 1; i <= n; ++i)
            fact[i] = fact[i - 1] * i;
        ifact[n] = fact[n].inv();
        for (int i = n; i >= 1; --i)
            ifact[i - 1] = ifact[i] * i;
    }

    mint operator()(int n, int k)
    {
        if (k < 0 || k > n)
            return 0;
        return fact[n] * ifact[k] * ifact[n - k];
    }
};

#line 1 "EnumerativeCombinatorics/binomial_coefficient_prime_mod.hpp"
#include <bits/stdc++.h>
using namespace std;

template <class mint>
class combination
{
private:
    vector<mint> fact, ifact;

public:
    combination(int n) : fact(n + 1), ifact(n + 1)
    {
        assert(n < mint::mod());
        fact[0] = 1;
        for (int i = 1; i <= n; ++i)
            fact[i] = fact[i - 1] * i;
        ifact[n] = fact[n].inv();
        for (int i = n; i >= 1; --i)
            ifact[i - 1] = ifact[i] * i;
    }

    mint operator()(int n, int k)
    {
        if (k < 0 || k > n)
            return 0;
        return fact[n] * ifact[k] * ifact[n - k];
    }
};

Back to top page