Struct 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, balls: usize, boxes: usize) -> N

重複組合せ

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