CombinationLucas 構造体

Lucas の定理を用いた二項係数計算用ライブラリ [詳解]

#include "combination_lucas.hpp"

公開メンバ関数
	CombinationLucas (int mod)
	Lucas の定理を用いて二項係数を計算するための前計算をする
ll	comb (int n, int r)
	nCr mod を返す

詳解

Lucas の定理を用いた二項係数計算用ライブラリ

Lucas の定理 p を素数とし、n, r を非負整数とする。 また、n = n[k]p^k + n[k-1]p^(k-1) + ... + n[1]p + n[0], r = r[k]p^k + r[k-1]p^(k-1) + ... + r[1]p + r[0] とする。

このとき、nCr(mod p) = Π[k=0~N]n[k]Cr[k]

combination_lucas.hpp の 14 行目に定義があります。

構築子と解体子

CombinationLucas()

CombinationLucas::CombinationLucas ( int mod )

inline

Lucas の定理を用いて二項係数を計算するための前計算をする

覚え書き

O(mod)

combination_lucas.hpp の 17 行目に定義があります。

関数詳解

comb()

ll CombinationLucas::comb ( int n, int r )

inline

nCr mod を返す

覚え書き

O(log(n))

combination_lucas.hpp の 28 行目に定義があります。

参照先 comb().

---

この構造体詳解は次のファイルから抽出されました:

• mod/combination_lucas.hpp