Struct cp_library_rs::number_theory::comb::Comb

pub struct Comb<N: NumProbability> { /* private fields */ }

二項係数を高速に求める

• 前計算: $O(N)$ 時間
• クエリ: $O(1)$ 時間

Implementations

impl<N: NumProbability> Comb<N>

pub fn new(max_size: usize) -> Self

サイズmax_sizeで配列を初期化する

pub fn comb(&self, n: usize, r: usize) -> N

n個からr個選ぶ組合せ

• 時間計算量: $O(1)$

pub fn perm(&self, n: usize, r: usize) -> N

n個からr個を選び並べる順列

• 時間計算量: $O(1)$

pub fn comb_with_rep(&self, n: usize, r: usize) -> N

重複組合せ

• n個の区別しない玉をr個の区別する箱に入れる組合せ
• 時間計算量: $O(1)$