Struct Combinatorics 

pub struct Combinatorics<const MOD: i64> { /* private fields */ }

階乗と逆階乗を前計算し、順列・組合せを高速に計算します。

法 MOD 上の階乗・順列・組合せを前計算して扱います。

new(max_n) は 0..=max_n の階乗と逆階乗を保存します。以後、引数 n がこの範囲内なら n!、順列 nPr、組合せ nCr を O(1) で求められます。r > n の順列・組合せは 0 です。

MOD は素数であり、max_n < MOD を満たす必要があります。 構築の計算量は O(max_n + log MOD)、使用メモリは O(max_n) です。

Panics

• MOD <= 1 の場合
• max_n >= MOD の場合
• 前計算範囲を超える n を指定した場合

Examples

use atcoder::math::combinatorics::Combinatorics;

let comb = Combinatorics::<998_244_353>::new(10);

assert_eq!(comb.factorial(5).value(), 120);
assert_eq!(comb.permutation(5, 2).value(), 20);
assert_eq!(comb.combination(5, 2).value(), 10);

Implementations

impl<const MOD: i64> Combinatorics<MOD>

pub fn new(max_n: usize) -> Self

0..=max_n の階乗と逆階乗を法 MOD で前計算します。

MOD は 1 より大きい素数、かつ max_n < MOD でなければなりません。

計算量は O(max_n + log MOD)、使用メモリは O(max_n) です。

Panics

MOD <= 1、max_n >= MOD、または max_n が i64 に収まらない場合に panic します。

pub fn max_n(&self) -> usize

前計算した最大の引数 n を返します。利用可能な範囲は 0..=max_n() です。

pub fn factorial(&self, n: usize) -> ModInt<MOD>

n! を法 MOD で返します。

計算量は O(1) です。

Panics

n > max_n() の場合に panic します。

pub fn permutation(&self, n: usize, r: usize) -> ModInt<MOD>

順列 nPr = n! / (n-r)! を法 MOD で返します。

r > n の場合は 0 を返します。n は前計算範囲内である必要があります。 計算量は O(1) です。

pub fn combination(&self, n: usize, r: usize) -> ModInt<MOD>

組合せ nCr を法 MOD で返します。

r > n の場合は 0 を返します。n は前計算範囲内である必要があります。 計算量は O(1) です。

Trait Implementations

impl<const MOD: i64> Clone for Combinatorics<MOD>

fn clone(&self) -> Combinatorics<MOD>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<const MOD: i64> Debug for Combinatorics<MOD>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.