組み合わせ

Combination

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

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

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

実装

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

剰余の世界での四則演算

(参考)

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

nの値が小さければ、「パスカルの三角形」によっても求めることが可能です。
n<=5000程度が限界ですが、以下のような場合に使えます。

  • modintではない値を求める場合
  • その選び方をされる確率の計算

はこちらの方法を使うのが良いでしょう。

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

 

関連問題

組み合わせに関する公式

二項定理

     \begin{equation*} \sum_{k=0}^n _{n}C_{k} \, x^k \, y^{n-k} = (x+y)^n \end{equation*}

式変形により色々導き出せます。

     \begin{equation*} \sum_{k=0}^n _{n}C_{k} = 2^n \end{equation*} \begin{equation*} \sum_{k=1}^n k\cdot _{n}C_{k} = n \cdot 2^{n-1} \end{equation*} \begin{equation*} \sum_{i=0}^k _{n+i}C_{n} = _{n+k+1}C_{n+1} \end{equation*}

その他

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

関連するABCの問題

重複組み合わせ

同じものをいくつでも選んで良いときの組み合わせ数

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

その他

同じモノが有限個ある時の組み合わせ数

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

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

x及びyすべてを区別出来ると考えた時、全体の並べ方は(p+q)!通りです。
そこからxの並べ方の種類p!とyの並べ方の種類q!を割れば、区別しない場合の並べ方のパターン数になります。

参考

組み合わせの全列挙

DFSで実装できます。

使い方

 

(参考)

関連問題

順列

完全順列(撹乱順列)

1,2,⋯,n を並び替えてできる順列のうち,全てのiに対してAi != iである数列

この順列の個数a_nは以下の式で表せる

     \begin{equation*} a_n = n! \sum_{k=2}^n \frac{( -1)^n}{k!} \end{equation*}

完全順列の個数a_nのことをモンモール数という。

この式は包除原理によって導出することが出来る。

(参考)

関連問題

その他

  • (Bullet) (ABC168)
    禁止ペアがある時の組み合わせ