数え上げ（mod付き）
(algorithm/Math/Combinatorics/combination.hpp)

• View this file on GitHub
• Last update: 2025-07-03 00:41:25+09:00
• Include: #include "algorithm/Math/Combinatorics/combination.hpp"

概要

ある場合の数を，素数 $p$ を法として $\bmod$ を取りながら数え上げる．

計算量は，前処理が $\mathcal{O}(N)$ ，各クエリ処理が $\mathcal{O}(1)$ となる．

説明

algorithm::Combination

メンバ関数	説明	計算量
Combination<p>(n)	コンストラクタ	$\mathcal{O}(N)$
factorial(n)	$n! \mod p$ を返す．	$\mathcal{O}(1)$
inverse(n)	$n^{-1} \mod p$ を返す．	$\mathcal{O}(1)$
inverse_factorial(n)	$(n!)^{-1} \mod p$ を返す．	$\mathcal{O}(1)$
nPk(n,k)	$_n \mathrm{P}_k \mod p$ を返す．	$\mathcal{O}(1)$
nCk(n,k)	$_n \mathrm{C}_k \mod p$ を返す．	$\mathcal{O}(1)$
nHk(n,k)	$_n \mathrm{H}_k \mod p$ を返す．	$\mathcal{O}(1)$

参考

1. “数え上げ数学”. Wikipedia. https://ja.wikipedia.org/wiki/数え上げ数学.
2. drken1215. “よくやる二項係数 (nCk mod. p)、逆元 (a^-1 mod. p) の求め方”. HatenaBlog. https://drken1215.hatenablog.com/entry/2018/06/08/210000.
3. ngtkana. “1..=N の階乗逆数・ただの逆数を O(N) 時間で前計算する方法（mod p）” https://ngtkana.hatenablog.com/entry/2025/05/11/105210.
4. rsk0315. “mod についてふんわりとしか理解していない競プロ er のみなさん”. HatenaBlog. https://rsk0315.hatenablog.com/entry/2023/05/05/221524.
5. “競プロでよく使う二項係数(nCk)を素数(p)で割った余りの計算と逆元のまとめ”. アルゴリズムロジック. https://algo-logic.info/combination/.

問題

• “D - Factorization”. AtCoder Beginner Contest 110. https://atcoder.jp/contests/abc110/tasks/abc110_d.
• “E - Max-Min Sum”. AtCoder Beginner Contest 151. https://atcoder.jp/contests/abc151/tasks/abc151_e.

Verified with

• verify/yuki-117-combination.test.cpp

Code

#ifndef ALGORITHM_COMBINATION_HPP
#define ALGORITHM_COMBINATION_HPP 1

#include <cassert>
#include <vector>

namespace algorithm {

template <int mod>
class Combination {
    static_assert(mod >= 2);

    int m_sz;
    std::vector<long long> m_fact;      // m_fact[n]:=(nの階乗).
    std::vector<long long> m_inv;       // m_inv[n]:=(nの逆元).
    std::vector<long long> m_inv_fact;  // m_inv_fact[n]:=(nの階乗の逆元).

    void build(int n) {
        if(n <= m_sz) return;
        m_fact.resize(n);
        m_inv.resize(n);
        m_inv_fact.resize(n);
        for(int i = m_sz; i < n; ++i) {
            m_fact[i] = m_fact[i - 1] * i % mod;
            m_inv[i] = mod - m_inv[mod % i] * (mod / i) % mod;
            m_inv_fact[i] = m_inv_fact[i - 1] * m_inv[i] % mod;
        }
        m_sz = n;
    }

public:
    Combination() : Combination(2) {}
    explicit Combination(int n) : m_sz(2), m_fact(n), m_inv(n), m_inv_fact(n) {
        assert(n >= 2);
        m_fact[0] = m_fact[1] = 1;
        m_inv[1] = 1;
        m_inv_fact[0] = m_inv_fact[1] = 1;
        build(n);
    }

    static constexpr int modulus() { return mod; }
    // 階乗．O(1).
    long long factorial(int n) {
        assert(n >= 0);
        build(n + 1);
        return m_fact[n];
    }
    // 逆元．O(1).
    long long inverse(int n) {
        assert(n >= 1);
        build(n + 1);
        return m_inv[n];
    }
    // 階乗の逆元．O(1).
    long long inverse_factorial(int n) {
        assert(n >= 0);
        build(n + 1);
        return m_inv_fact[n];
    }
    // 順列．O(1).
    long long nPk(int n, int k) {
        assert(n >= 0);
        assert(k >= 0);
        if(n < k) return 0;
        build(n + 1);
        return m_fact[n] * m_inv_fact[n - k] % mod;
    }
    // 組合せ．O(1).
    long long nCk(int n, int k) {
        assert(n >= 0);
        assert(k >= 0);
        if(n < k) return 0;
        build(n + 1);
        return m_fact[n] * m_inv_fact[n - k] % mod * m_inv_fact[k] % mod;
    }
    // 重複組合せ．O(1).
    long long nHk(int n, int k) {
        assert(n >= 0);
        assert(k >= 0);
        if(k == 0) return 1;
        if(n == 0) return 0;
        return nCk(k + n - 1, k);
    }
};

using Combination998244353 = Combination<998'244'353>;
using Combination1000000007 = Combination<1'000'000'007>;

}  // namespace algorithm

#endif

#line 1 "algorithm/Math/Combinatorics/combination.hpp"



#include <cassert>
#include <vector>

namespace algorithm {

template <int mod>
class Combination {
    static_assert(mod >= 2);

    int m_sz;
    std::vector<long long> m_fact;      // m_fact[n]:=(nの階乗).
    std::vector<long long> m_inv;       // m_inv[n]:=(nの逆元).
    std::vector<long long> m_inv_fact;  // m_inv_fact[n]:=(nの階乗の逆元).

    void build(int n) {
        if(n <= m_sz) return;
        m_fact.resize(n);
        m_inv.resize(n);
        m_inv_fact.resize(n);
        for(int i = m_sz; i < n; ++i) {
            m_fact[i] = m_fact[i - 1] * i % mod;
            m_inv[i] = mod - m_inv[mod % i] * (mod / i) % mod;
            m_inv_fact[i] = m_inv_fact[i - 1] * m_inv[i] % mod;
        }
        m_sz = n;
    }

public:
    Combination() : Combination(2) {}
    explicit Combination(int n) : m_sz(2), m_fact(n), m_inv(n), m_inv_fact(n) {
        assert(n >= 2);
        m_fact[0] = m_fact[1] = 1;
        m_inv[1] = 1;
        m_inv_fact[0] = m_inv_fact[1] = 1;
        build(n);
    }

    static constexpr int modulus() { return mod; }
    // 階乗．O(1).
    long long factorial(int n) {
        assert(n >= 0);
        build(n + 1);
        return m_fact[n];
    }
    // 逆元．O(1).
    long long inverse(int n) {
        assert(n >= 1);
        build(n + 1);
        return m_inv[n];
    }
    // 階乗の逆元．O(1).
    long long inverse_factorial(int n) {
        assert(n >= 0);
        build(n + 1);
        return m_inv_fact[n];
    }
    // 順列．O(1).
    long long nPk(int n, int k) {
        assert(n >= 0);
        assert(k >= 0);
        if(n < k) return 0;
        build(n + 1);
        return m_fact[n] * m_inv_fact[n - k] % mod;
    }
    // 組合せ．O(1).
    long long nCk(int n, int k) {
        assert(n >= 0);
        assert(k >= 0);
        if(n < k) return 0;
        build(n + 1);
        return m_fact[n] * m_inv_fact[n - k] % mod * m_inv_fact[k] % mod;
    }
    // 重複組合せ．O(1).
    long long nHk(int n, int k) {
        assert(n >= 0);
        assert(k >= 0);
        if(k == 0) return 1;
        if(n == 0) return 0;
        return nCk(k + n - 1, k);
    }
};

using Combination998244353 = Combination<998'244'353>;
using Combination1000000007 = Combination<1'000'000'007>;

}  // namespace algorithm

Back to top page