組合せ・順列・重複組合せ (素数 mod) (EnumerativeCombinatorics/combination_prime_mod.hpp)

View this file on GitHub
View document part on GitHub
Last update: 2026-05-17 15:50:36+09:00
Include: #include "EnumerativeCombinatorics/combination_prime_mod.hpp"

組合せ・順列・重複組合せ (素数 mod)

組合せ $nCr$、順列 $nPr$、重複組合せ $nHr$ を素数 $m$ で割った余りとして計算できます。

階乗およびその逆元を前計算することで、各値を定数時間で取得できます。テンプレート引数 mint には、atcoder::modint 系の型を指定することを前提としています。

参考

AtCoder解説放送ライブラリ集

コンストラクタ

combinatorics<mint>(int n)

$0$ 以上 $n$ 以下の階乗および階乗の逆元を前計算します。

これにより、任意の $0 \leq r \leq a \leq n$ に対して、組合せ $aCr$ および順列 $aPr$ を定数時間で計算できます。

また、重複組合せ $aHr$ は次の式を用いて計算されます。

\[aHr = \binom{a + r - 1}{r}\]

そのため、H(a, r) を呼び出す場合は、$a + r - 1 \leq n$ を満たすように前計算サイズを指定する必要があります。

制約

$0 \leq n <$ mint::mod()

計算量

$O(n)$

メンバ関数

operator()

mint operator()(int n, int k)

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

C(n, k) と同じ値を返します。

$n < 0$、$k < 0$、または $k > n$ の場合は $0$ を返します。

制約

$0 \leq n \leq$ コンストラクタで指定した値

計算量

$O(1)$

C

mint C(int n, int r)

組合せ $nCr$ を法 $m$ で割った余りとして返します。

\[nCr = \frac{n!}{r!(n-r)!}\]

$n < 0$、$r < 0$、または $r > n$ の場合は $0$ を返します。

制約

$0 \leq n \leq$ コンストラクタで指定した値

計算量

$O(1)$

P

mint P(int n, int r)

順列 $nPr$ を法 $m$ で割った余りとして返します。

\[nPr = \frac{n!}{(n-r)!}\]

$n < 0$、$r < 0$、または $r > n$ の場合は $0$ を返します。

制約

$0 \leq n \leq$ コンストラクタで指定した値

計算量

$O(1)$

H

mint H(int n, int r)

重複組合せ $nHr$ を法 $m$ で割った余りとして返します。

\[nHr = \binom{n + r - 1}{r}\]

$n$ 種類のものから重複を許して $r$ 個選ぶ場合の数を表します。

$n < 0$ または $r < 0$ の場合は $0$ を返します。また、$n = 0$ の場合は、$r = 0$ のときのみ $1$ を返し、それ以外では $0$ を返します。

制約

$0 \leq n$
$0 \leq r$
$n = 0$ または $n + r - 1 \leq$ コンストラクタで指定した値

計算量

$O(1)$

Verified with

Code

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

template <class mint>
class combinatorics
{
private:
    int max_n;
    vector<mint> fact, ifact;

public:
    combinatorics(int n) : max_n(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)
    {
        return C(n, k);
    }

    // nCr
    mint C(int n, int r)
    {
        if (n < 0 || r < 0 || r > n)
            return 0;
        assert(n <= max_n);

        return fact[n] * ifact[r] * ifact[n - r];
    }

    // nPr
    mint P(int n, int r)
    {
        if (n < 0 || r < 0 || r > n)
            return 0;
        assert(n <= max_n);

        return fact[n] * ifact[n - r];
    }

    // nHr
    mint H(int n, int r)
    {
        if (n < 0 || r < 0)
            return 0;

        if (n == 0)
            return r == 0 ? 1 : 0;

        return C(n + r - 1, r);
    }
};

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

template <class mint>
class combinatorics
{
private:
    int max_n;
    vector<mint> fact, ifact;

public:
    combinatorics(int n) : max_n(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)
    {
        return C(n, k);
    }

    // nCr
    mint C(int n, int r)
    {
        if (n < 0 || r < 0 || r > n)
            return 0;
        assert(n <= max_n);

        return fact[n] * ifact[r] * ifact[n - r];
    }

    // nPr
    mint P(int n, int r)
    {
        if (n < 0 || r < 0 || r > n)
            return 0;
        assert(n <= max_n);

        return fact[n] * ifact[n - r];
    }

    // nHr
    mint H(int n, int r)
    {
        if (n < 0 || r < 0)
            return 0;

        if (n == 0)
            return r == 0 ? 1 : 0;

        return C(n + r - 1, r);
    }
};