二項係数 (lib/math/combination.hpp)

• View this file on GitHub
• Last update: 2025-05-22 02:52:27+09:00
• Include: #include "lib/math/combination.hpp"

Depends on

• Montgomery modular multiplication (lib/internal/internal_math.hpp)
• lib/math/modint.hpp

Required by

• lib/algorithm/offline_binomial_sum.hpp
• lib/fft/formal_power_series.hpp
• lib/math/bell.hpp
• lib/math/enumeration.hpp

Verified with

• test/aoj/dpl/bell.test.cpp
• test/aoj/dpl/stirling.test.cpp
• test/yosupo/enumerative_conbinatorics/bell_number.test.cpp
• test/yosupo/polynomial/division_of_polynomials.test.cpp
• test/yosupo/polynomial/exp_of_formal_power_series.test.cpp
• test/yosupo/polynomial/inv_of_formal_power_series.test.cpp
• test/yosupo/polynomial/log_of_formal_power_series.test.cpp
• test/yosupo/polynomial/multipoint_evaluation.test.cpp
• test/yosupo/polynomial/polynomial_interpolation.test.cpp
• test/yosupo/polynomial/polynomial_taylor_shift.test.cpp
• test/yosupo/polynomial/pow_of_formal_power_series.test.cpp
• test/yukicoder/2206.test.cpp

Code

#pragma once
#include <cassert>
#include <concepts>
#include <vector>
#include "math/modint.hpp"

/// @brief 二項係数
template <class mint = modint998>
requires(std::derived_from<mint, internal::modint_base>)
struct Combination {
    Combination() : _fact(), _inv(), _finv() {}

    mint operator()(int n, int k) {
        if (n < k || n < 0 || k < 0) return 0;
        _init(n);
        return _fact[n] * _finv[k] * _finv[n - k];
    }

    mint fact(int x) {
        assert(x >= 0);
        _init(x);
        return _fact[x];
    }

    mint finv(int x) {
        assert(x >= 0);
        _init(x);
        return _finv[x];
    }

    mint naive(int n, int k) const {
        if (n < k || n < 0 || k < 0) return 0;
        if (n - k < k) k = n - k;
        mint res = 1;
        for (int i = 0; i < k; ++i) {
            res *= n - i;
            res /= i + 1;
        }
        return res;
    }

    mint permu(int n, int k) {
        if (n < k || n < 0 || k < 0) return 0;
        _init(n);
        return _fact[n] * _finv[n - k];
    }

  private:
    static constexpr int _mod = mint::mod();
    std::vector<mint> _fact, _inv, _finv;

    void _init(int n) {
        if ((int)_fact.size() > n) return;
        int m = _fact.size();
        _fact.resize(n + 1);
        for (int i = m; i <= n; ++i) {
            if (i == 0) _fact[i] = 1;
            else _fact[i] = _fact[i - 1] * i;
        }
        _inv.resize(n + 1);
        for (int i = m; i <= n; ++i) {
            if (i <= 1) _inv[i] = 1;
            else _inv[i] = -_inv[_mod % i] * (_mod / i);
        }
        _finv.resize(n + 1);
        for (int i = m; i <= n; ++i) {
            if (i == 0) _finv[i] = 1;
            else _finv[i] = _finv[i - 1] * _inv[i];
        }
    }
};

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/resolver.py", line 291, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 242, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 479, in update
    self._resolve(pathlib.Path(included), included_from=path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 286, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
competitive_verifier.oj.verify.languages.cplusplus_bundle.BundleErrorAt: math/modint.hpp: line -1: no such header

Back to top page