MOD 組み合わせ nCk
(library/number/mod/mod_combination.hpp)

• View this file on GitHub
• Last update: 2026-01-20 20:11:22+09:00
• Include: #include "library/number/mod/mod_combination.hpp"

MOD 組み合わせ nCk

できること

• MOD下で、 $nCk$ を求める

計算量

$O(logM)$

使い方

long long comb = mod_combination(n, k, MOD);

Depends on

• MOD 階乗 (library/number/mod/mod_factorial.hpp)
• MOD Fermatの小定理 (library/number/mod/mod_inverse.hpp)
• MOD 二分累乗 (library/number/mod/mod_pow.hpp)

Verified with

• MOD 組み合わせ nCkのテスト (tests/number.mod.mod_combination.test.cpp)

Code

#pragma once
#include "library/number/mod/mod_inverse.hpp"
#include "library/number/mod/mod_factorial.hpp"
long long mod_combination(int n, int k, long long m) {
    if (k < 0 or n < k) return 0ll;
    return mod_factorial(n, m) * mod_inverse(mod_factorial(k, m), m) % m *
           mod_inverse(mod_factorial(n - k, m), m) % m;
}

#line 2 "library/number/mod/mod_pow.hpp"
long long mod_pow(long long a, long long n, long long m) {
    long long res = 1ll;
    while (n > 0) {
        if (n & 1) res = res * a % m;
        a = a * a % m;
        n >>= 1ll;
    }
    return res;
}
#line 3 "library/number/mod/mod_inverse.hpp"
long long mod_inverse(long long a, long long m) { return mod_pow(a, m - 2, m); }
#line 2 "library/number/mod/mod_factorial.hpp"
vector<long long> _mf_memo;
long long mod_factorial(int x, long long m) {
    if ((int)_mf_memo.size() > x) return _mf_memo[x];
    if (_mf_memo.empty()) _mf_memo.push_back(1);
    for (int i = _mf_memo.size(); i <= x; ++i)
        _mf_memo.push_back(_mf_memo.back() * i % m);
    return _mf_memo[x];
}
#line 4 "library/number/mod/mod_combination.hpp"
long long mod_combination(int n, int k, long long m) {
    if (k < 0 or n < k) return 0ll;
    return mod_factorial(n, m) * mod_inverse(mod_factorial(k, m), m) % m *
           mod_inverse(mod_factorial(n - k, m), m) % m;
}

Back to top page