algorithm - 固定 n モジュロ m の最初の r 二項係数の合計を求めるアルゴリズム

Question

固定 n の最初の r 二項係数の合計を見つけようとしています。

(nC1 + nC2 + nC3 + ... + nCr) % M

ここで、r < = n です。

この問題を解決する効率的なアルゴリズムはありますか?

Answer 1

私の最初の回答は、いくつかの理由で満足のいくものではありませんでした。その理由の 1 つは、私が参照した論文が理解しにくく、実装が難しいことです。そこで、以下の問題に対する別の解決策を提案します。

固定n , nC0 + nC1 + ... + nC(r-1), modulo Mの最初の r 二項係数の合計を計算したい. さらに、r が n よりもはるかに小さい場合があるため、n をインクリメントして値を取得することは、r をインクリメントするよりもはるかに効率が悪い可能性があります。nCknC(k-1)

アイデアは次のとおりです。最初に、r > n/2 の場合nC0 + ... + nC(r-1) = 2^n - (nCr + ... + nCn) = 2^n - (nC0 + ... + nC(n-r))、nr < n/2 であることに注意してください。したがって、問題を r <= n/2 の場合に減らしました。

次に、ID を適用します

nCk = n!/(k!(n-k)!) = n!/((k-1)!(n-(k-1)!) x (n-k+1)/k = nC(k-1) x (n-k+1)/k

合計の項を順番に計算します。整数のサイズに制限がない場合、計算できます

sum = 0;
nCi = 1; // i=0
for i = 1 to r-1
  sum += nCi;
  nCi *= (n-k+1);
  nCi /= k;
sum %= M;

これに関する問題は、数値 nCi (したがって合計) が膨大になる可能性があるため、大きな整数を使用する必要があり、計算が遅くなることです。ただし、mod M の結果のみが必要なのでint、ループ内で mod M の計算を実行する場合は s を使用できます。

Sum と Product は単純な mod M ですが、除算はそうで​​はありません。nCi を k mod 10^6 で割るには、nCi と k を 2^s 5^tu の形式で記述する必要があります。ここで、u は 10^6 と互いに素です。次に、指数を引き、u mod 10^6 の逆数を掛けます。nCi をその形式で記述するには、n-k+1 もその形式で記述する必要があります。

k と n-k+1 を 2^s 5^tu の形式で u が 10^6 と互いに素になるようにするには、2 で割って割り切れるかどうかを繰り返しチェックし、5 についても同じようにします。もっと速い方法があるはずです。

いずれにせよ、アルゴリズムは O(r) になりました。これは、合計の単純な数式の発見を除いて、可能な限り最速のようです。