巨大なnについての二項係数
巨大なn(10^9)について二項係数を求める場合、n!の計算がO(n)なので間に合わない
\binom{n}{k} = \frac{n!}{k!(n-k)!} = \frac{n!}{(n-k)!} \frac{1}{k!}
と変形すればそれぞれはO(k)で求められる
実装例
pythondef naive_comb(n, k, MOD=MOD):
assert n >= 0
assert k >= 0
if n < k:
return 0
k = min(k, n - k)
a = 1
b = 1
for i in range(k):
a *= (n - i)
a %= MOD
b *= (i + 1)
b %= MOD
return (a * mod_inverse(b, MOD)) % MODmod_inverseについては mod Pでの逆元
from mod Pでの組み合わせ
Related Pages
- →僕のatcoderの学び方(〜緑)×僕のatcoderの学び方(〜青)×ARC106×気づきの言語化×結晶化×変形テクニックに名前をつける×行列の半分×二項定理×足し算の順序の変更×概念のハンドル×テストできるスニペットライブラリ×unionfind×mod Pでの組み合わせ×educational_dp_contest×動的計画法×atcoder_library_practice_contest×atcoder_library×帰着する力×帰着訓練→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]