Binomial Coefficient (Arbitrary Mod)
(math/binomial_coefficient_arbitrary_mod.hpp)

• View this file on GitHub
• Last update: 2026-05-18 11:48:23+09:00
• Include: #include "math/binomial_coefficient_arbitrary_mod.hpp"

概要

• 任意 mod（合成数 OK）に対する二項係数 $\binom{n}{k} \bmod m$ を計算する。
• mod を素因数分解し、各素数べきに対して Lucas の定理（の一般化）で計算したものを CRT で合成する。

使い方

• binomial_coefficient_arbitrary_mod<id = -1>: mod を実行時に切り替える。id を変えれば独立した静的状態を持てる（atcoder::dynamic_modint と同じ流儀）。
• set_mod(mod): mod を設定する。キャッシュもリセットされる。
• C(n, k): $\binom{n}{k} \bmod m$ を long long で返す。

注意

• 同じ id に対して set_mod を呼び直すと過去のキャッシュは無効化される。複数 mod を同時に扱いたい場合は id を分けてインスタンス化する。

Depends on

• math/factorize.hpp

Verified with

• test/library-checker/binomial_coefficient.test.cpp

Code

#pragma once
#include <cassert>
#include <map>
#include <vector>
#if __has_include(<atcoder/math.hpp>)
#include <atcoder/math.hpp>
#else
#include "atcoder/math.hpp"
#endif
#include "math/factorize.hpp"
template <int id = -1>
struct binomial_coefficient_arbitrary_mod {
    static void set_mod(int mod) {
        assert(1 <= mod);
        m = mod;
        factors = factorize(m);
        f.assign(factors.size(), {});
        inv_f.assign(factors.size(), {});
        max_size = 0;
    }
    static long long C(long long n, long long k) {
        if (m == 1 || n < 0 || n < k || k < 0) return 0;
        ensure(n);
        long long r = n - k;
        std::vector<long long> rems(factors.size()), mods(factors.size());
        int idx = 0;
        for (auto [p, q] : factors) {
            long long p_q = pow_ll(p, q);
            mods[idx] = p_q;
            long long e1 = 0, e2 = 0;
            for (long long p_i = p_q;;) {
                e1 += n / p_i - k / p_i - r / p_i;
                if (p_i > n / p) break;
                p_i *= p;
            }
            for (long long p_i = p;;) {
                e2 += n / p_i - k / p_i - r / p_i;
                if (p_i > n / p) break;
                p_i *= p;
            }
            atcoder::internal::barrett bt((unsigned int)(p_q));
            long long delta = p == 2 && q >= 3 ? 1 : -1;
            long long rem = delta == -1 && e1 & 1 ? p_q - 1 : 1;
            rem = bt.mul(rem, atcoder::pow_mod(p, e2, p_q));
            for (long long p_i = 1;;) {
                rem = bt.mul(rem, f[idx][(n / p_i) % p_q]);
                rem = bt.mul(rem, inv_f[idx][(k / p_i) % p_q]);
                rem = bt.mul(rem, inv_f[idx][(r / p_i) % p_q]);
                if (p_i > n / p) break;
                p_i *= p;
            }
            rems[idx] = rem;
            idx++;
        }
        return atcoder::crt(rems, mods).first;
    }

private:
    static void ensure(long long n) {
        if (max_size > n) return;
        int idx = 0;
        for (auto [p, q] : factors) {
            long long p_q = pow_ll(p, q);
            int sz = f[idx].size();
            if ((long long)sz > std::min(p_q - 1, n) + 1) continue;
            f[idx].resize(std::min(p_q - 1, n) + 1);
            inv_f[idx].resize(std::min(p_q - 1, n) + 1);
            max_size = std::max(max_size, std::min(p_q - 1, n) + 1);
            atcoder::internal::barrett bt((unsigned int)(p_q));
            for (int i = sz; i <= std::min(p_q - 1, n); i++) {
                if (i == 0) {
                    f[idx][i] = 1;
                } else {
                    if (i % p == 0) {
                        f[idx][i] = f[idx][i - 1];
                    } else {
                        f[idx][i] = bt.mul(f[idx][i - 1], i);
                    }
                }
                inv_f[idx][i] = atcoder::inv_mod(f[idx][i], p_q);
            }
            idx++;
        }
    }
    static long long pow_ll(long long x, long long n) {
        assert(0 <= n && 1 <= m);
        long long r = 1, y = x;
        while (n) {
            if (n & 1) r *= y;
            n >>= 1;
            if (n) y *= y;
        }
        return r;
    }
    static inline long long m = -1;
    static inline long long max_size = 0;
    static inline std::map<long long, int> factors{};
    static inline std::vector<std::vector<long long>> f{};
    static inline std::vector<std::vector<long long>> inv_f{};
};

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.13/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.13/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
  File "/opt/hostedtoolcache/Python/3.12.13/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 400, in update
    raise BundleErrorAt(path, i + 1, "unable to process #include in #if / #ifdef / #ifndef other than include guards")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: math/binomial_coefficient_arbitrary_mod.hpp: line 8: unable to process #include in #if / #ifdef / #ifndef other than include guards

Back to top page