トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

階乗のmod逆元 - 組み合わせ

[アルゴリズム]

階乗のmod逆元 - 組み合わせ

の流れで解いていく

  問題設定

nCrの組み合わせ数の算出方法にはいろいろな方法があるが、ここでは階乗のmod逆元を使用したアルゴリズムについてフォーカスをあてたい。

nCr , つまり n個からr選んだときの全ての組み合わせを求めます。組み合わせ とは、n個から重複なしにr個選んだ数のこととします。

数学的には、 nCr = n! / r! * ( n - r ) ! になります

素朴に

+ combination-naive.rb

累積和

  • imos法・累積和 でやったように、
    • まず必要な分だけ配列を用意する
    • クエリを仕込む
    • 配列全体に array[n] *= array[n-1] を実行する

+ combination-cumsum.rb

階乗のmod逆元 + 繰り返し2乗法

  • 山場である。巨大な組み合わせ計算の際に以下のような分数の計算(割り算)をしたい
    • fact(n) / (fact(r) * fact(n-r))
  • fact(r) は階乗なので、フェルマーの小定理 が使える
    • これは、ある数xのmod p(pは素数)上での逆数x'はx' = x ^ (p - 2)で計算できるというものである。

繰り返し2乗法 は別にページを書いているので、それを参照してほしい

  • EDIT: 2018/09/12, 1C1, 2C2 などの例外に対処するコードを追記

+ combination-cumsum.rb

お名前: コメント: