固定nの最初のr個の二項係数の合計を見つけようとしています。
ここで、r <= nです。
この問題を解決するための効率的なアルゴリズムはありますか？
固定のための「最初の」二項係数という注意nですnC0。しましょうf(n) = nC0 + nC1 + ... + nC(r-1)。「パスカルの三角形」のアイデンティティnCk = (n-1)C(k-1) + (n-1)Ckを使用して、
nC0 + nC1 + nC2 + ... + nC（r-1）
=（n-1）C（-1）+（n-1）C0 +（n-1）C0 +（n-1）C1 +（ n-1）C1 +（n-1）C2 + ... +（n-1）C（r-2）+（n-1）C（r-1）
= 2 [（n-1）C0 + （n-1）C1 +（n-1）C2 + ... +（n-1）C（r-2）] +（n-1）C（r-1）
= 2 [（n-1） C0 + ... +（n-1）C（r-1）]-（n-1）C（r-1）、
つまり、 f(n) = 2f(n-1) - (n-1)C(r-1) 各合計は、前を2倍にして、を引くことにより、前から計算できます (n-1)C(r-1) 。
たとえば、の場合r=3、
f（0）= 1、
f（1）= 1 + 1 = 2 = 2f（0）-0C2、
f（2）= 1 + 2 + 1 = 4 = 2f（1）-1C2、
f（3）= 1 + 3 + 3 = 7 = 2f（2）-2C2、
f（4）= 1 + 4 + 6 = 11 = 2f（3）-3C2、
f（5）= 1 + 5 + 10 = 16 = 2f（ 4）-4C2、
等々。
mod mの計算を実行するには、二項係数を事前に計算する必要があります(n-1)C(r-1) mod m。場合m素数である、二項係数はmod mサイクル環状であるm^k（のパワーmよりも大きいですr-1）。mが素数の累乗である場合、結果はかなり複雑になります。（http://www.dms.umontreal.ca/~andrew/PDF/BinCoeff.pdfを参照してください。）mに複数の素因数がある場合、中国剰余定理を使用して計算を前のケースに減らすことができます。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加