MOD 階乗
(library/number/mod/mod_factorial.hpp)

• View this file on GitHub
• Last update: 2026-01-15 10:11:56+09:00
• Include: #include "library/number/mod/mod_factorial.hpp"

MOD 階乗

できること

• MOD下で、 $N!$ を求める
• メモ化してる

計算量

$O(N)$

使い方

long long fac = mod_factorial(x, MOD);

Required by

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

Verified with

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

Code

#pragma once
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 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];
}

Back to top page