組み合わせ(<a href="/ja/%E4%BA%8C%E9%A0%85%E4%BF%82%E6%95%B0">二項係数</a>)
$_nC_k = C(n, k) = \binom{n}{k} = \frac{n!}{k!(n-k)!}$
を大きな数n, kについて求めたいとする。
mod Pでの値で良いとする
<ul>
<li>それが求まれば複数の値から<a href="/ja/%E4%B8%AD%E5%9B%BD%E5%89%B0%E4%BD%99%E5%AE%9A%E7%90%86">中国剰余定理</a>で元の値が復元できるから</li>
</ul>
剰余を取った後で普通の割り算を行うことはできない。
そこで<a href="/ja/mod%20P%E3%81%A7%E3%81%AE%E9%80%86%E5%85%83">mod Pでの逆元</a>を計算して掛ける。
<ul>
<li>単発での計算なら対数オーダーで逆元を作成</li>
<li>大量に計算するなら<a href="/ja/%E9%80%86%E5%85%83%E3%83%86%E3%83%BC%E3%83%96%E3%83%AB">逆元テーブル</a>を作れば一つ当たりは定数オーダーになる<ul>
<li><a href="/ja/%E5%89%B0%E4%BD%99%E7%BE%A4%E9%80%86%E5%85%83%E6%BC%B8%E5%8C%96%E5%BC%8F%E3%81%AE%E5%B0%8E%E5%87%BA">剰余群逆元漸化式の導出</a></li>
</ul>
</li>
<li><a href="/ja/%E4%BA%8C%E9%A0%85%E4%BF%82%E6%95%B0%E3%83%86%E3%83%BC%E3%83%96%E3%83%AB">二項係数テーブル</a></li>
</ul>
<a href="/ja/%E5%B7%A8%E5%A4%A7%E3%81%AAn%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6%E3%81%AE%E4%BA%8C%E9%A0%85%E4%BF%82%E6%95%B0">巨大なnについての二項係数</a>

mod Pでの組み合わせ