二項係数(素数mod)
(Src/Number/BinomalCoefficients.hpp)

View this file on GitHub
Last update: 2024-06-30 16:42:17+09:00
Include: #include "Src/Number/BinomalCoefficients.hpp"

概要

素数 $P$ と $i = 0, 1, \dots, n$ について $i!$ と $x_{i}\times i!\equiv 1\pmod{P}$ なる $x_{i}$ を列挙する。

これによって素数 $P$ に対して $\binom{n}{r}$ 等が高速に求めることができる。

ライブラリの使い方

型

using Value = atcoder::modint

dynamic_modintだからちょっと遅いんだよな。うーーーん。流石にAt, ICPCでこれが原因で完数落とすことは無いと信じたいが….

コンストラクタ

(1) BinomalCoefficients(u32 M)

modを $M$ として初期化する。 $M$ が素数でないときassertに引っかかる。

reserve

void reserve(u32 n)

内部のコンテナのサイズを $n$ にする。現在のコンテナのサイズが $n$ より大きいときは何もしない。

F

Value F(i32 n)

$n$ が非負ならば $n!$ を、 $n$ が負ならば $(-n)!$ の乗法逆元を返す。

P

Value P(i32 p, i32 q)

$p$ 個の区別可能なボールから $q$ 個取り出し、それを一列に並べる通り数を返す。

C

Value C(i32 p, i32 q)

$p$ 個の区別可能なボールから $q$ 個取り出す通り数を返す。すなわち $\binom{p}{q}$ を返す。

H

Value H(i32 p, i32 q)

$p$ 種類のボールがそれぞれ無数にあるなかで、 $q$ 個取り出す通り数を返す。

いわゆる「 $p - 1$ 個の仕切りと $q$ 個のボールの並べ方」である。

B

Value B(const std::vector<i32>& b)

色 $0$ のボールが $b_0$ 個、色 $1$ のボールが $b_{1}$ 個…..

とあるなかで、それらすべてを一列に並べる通り数。ただし、同じ色のボールは区別がつかないとする。

Depends on

標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Verified with

Code

#pragma once

#include "../Template/TypeAlias.hpp"

#include <cassert>
#include <cmath>
#include <vector>
#include "atcoder/internal_math.hpp"
#include "atcoder/modint"

namespace zawa {

class BinomalCoefficients {
public:
    using Value = atcoder::modint;
    u32 mod() const {
        return Value::mod();
    }
private:
    usize n_{};
    std::vector<Value> F_{}, inv_{}, invF_{};
    constexpr bool need(usize n) const noexcept {
        return n_ <= n;
    }
    void expand(usize n) {
        F_.reserve(n + 1);
        inv_.reserve(n + 1);
        invF_.reserve(n + 1);
        for (usize i{n_} ; i <= n ; i++) {
            F_.emplace_back(F_.back() * Value{i});
            inv_.emplace_back(mod() - inv_[mod() % i] * (mod() / i));
            invF_.emplace_back(invF_.back() * inv_.back());
        }
        n_ = n + 1;
    }
public:
    constexpr usize size() const noexcept {
        return n_;
    }
    BinomalCoefficients(u32 M) 
        : n_{2u}, F_{Value::raw(1), Value::raw(1)}, inv_{Value{0}, Value::raw(1)},
        invF_{Value::raw(1), Value::raw(1)} {
            assert(atcoder::internal::is_prime_constexpr(M));
            Value::set_mod(M);
    }
    void reserve(usize newSize) {
        if (need(newSize)) {
            expand(newSize);
        }
    }
    Value F(i32 n) noexcept {
        if (need(std::abs(n))) expand(static_cast<usize>(std::abs(n)));
        return (n >= 0 ? F_[n] : invF_[-n]);
    }
    Value P(i32 p, i32 q) {
        if (q > p) return Value{}; 
        return F(p) * F(q - p);
    }
    Value C(i32 p, i32 q) {
        if (q > p) return Value{};
        return P(p, q) * F(-q);
    }
    Value H(i32 p, i32 q) {
        if (p == 0 and q == 0) return Value::raw(1);
        return C(p + q - 1, q);
    }
    Value B(const std::vector<i32>& b) {
        Value res{1};
        i32 sum{};
        for (i32 x : b) {
            res *= F(-x);
            sum += x;
        }
        res *= F(sum);
        return res;
    }
};

} // namespace zawa

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.13.5/x64/lib/python3.13/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.13.5/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
    ~~~~~~~~~~~~~~^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.5/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
                ~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.5/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 260, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: atcoder/internal_math.hpp: line -1: no such header

二項係数(素数mod) (Src/Number/BinomalCoefficients.hpp)

概要