組み合わせ

Combination

     \begin{equation*} _{n}C_{k} = \frac{n!}{k!(n-k)!} \end{equation*}

nCkは上記式で求めることが可能です。

分母の階乗要素と分子の階乗要素(の逆元)を予め求めてテーブル化しておくことにより、高速に計算が可能となります。

実装

ModInt構造体を用いて実装します。
ModInt構造体のコードについては下記ページから別途コピーする必要があります。

剰余の世界での四則演算

(参考)

パスカルの三角形による実装

nの値が十分に小さければ、下記の性質を利用した「パスカルの三角形」によっても求めることが可能です。
n<=5000程度までが限界なので、実用性は低いです。

     \begin{equation*} _{n}C_{k} = _{(n-1)}C_{(k-1)} + _{(n-1)}C_{k} \end{equation*}

関連するABCの問題

組み合わせ

同じモノがあるときの組み合わせ数

文字xを p 個,文字yを q 個使って出来る文字列は何通りあるか?

     \begin{equation*} N = \frac{(p+q)!}{p!q!} \end{equation*}

参考

組み合わせの全列挙

関連問題