c - 固定nの最初のr二項係数の合計を見つける方法は?

Question

nこのシリーズを解決する基本的な方法は既に試しましたが、 &の値が大きくなると時間がかかりますr。n時間の複雑さがOR r.Range r,n<=10^5の値に依存しない単一の式でこの式を減らす方法はありますか

注: ここで、つまり、このシリーズの最初の項のr < n合計を見つける必要があります。r+1

私はすでにこの質問を読みましたが、役に立ちません:

score 1 · Accepted Answer

N が大きい場合、二項係数はガウス曲線のように振る舞います (少なくとも中心値の場合)。これは、スターリングの公式から導き出すことができ、中心極限定理によってサポートされています。

次に、部分和を Error 関数で近似できます。

score 1 · Accepted Answer

私の知る限り、還元できるような表現はありません。ただし、次のように O(r) 時間の複雑さで実行できます。

^{A[i] がn} c _iを格納する配列 A を考えてみましょう。次に、A[i] = A[i-1].(n-i+1)/(i) であることを簡単に確認できます。

そう

A[0] = 1;
for(int i=1;i<=r;i++){
    A[i] = A[i-1].(n-i+1)/(i);
}
int ans = 0; //The required answer
for(int i=0;i<=r;i++){
    ans = ans+A[i];
}

2 に答える 2