Combination ( <a href="/en/binomial%20coefficient">binomial coefficient</a> )
$_nC_k = C(n, k) = \binom{n}{k} = \frac{n!}{k!(n-k)!}$
for large numbers n and k.
Assume that the value in mod P is good.
<ul>
<li>Once that is obtained, the original value can be restored by <a href="/en/Chinese%20remainder%20theorem">Chinese remainder theorem</a> from multiple values.</li>
</ul>
After taking the remainder, no ordinary division can be performed.
Then calculate and multiply <a href="/en/Inverse%20Element%20in%20mod%20P">Inverse Element in mod P</a>.
<ul>
<li>For single-shot calculations, create an inverse original in logarithmic order.
</li>
<li>If you want to calculate a large number of calculations, you can create an <a href="/en/inverse%20table">inverse table</a>, and each calculation will be of constant order.
 - <a href="/en/Derivation%20of%20the%20inverse%20modulo%20group%20asymptotic%20formula">Derivation of the inverse modulo group asymptotic formula</a>
<ul>
<li><a href="/en/binomial%20coefficient%20table">binomial coefficient table</a></li>
</ul>
</li>
<li><a href="/en/Binomial%20coefficient%20for%20huge%20n">Binomial coefficient for huge n</a>
</li>
</ul>
<hr>
This page is auto-translated from [/nishio/mod Pでの組み合わせ](<a href="https://scrapbox.io/nishio/mod">https://scrapbox.io/nishio/mod</a> Pでの組み合わせ) using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at <a href="https://twitter.com/nishio_en">@nishio_en</a>. I&#39;m very happy to spread my thought to non-Japanese readers.

Combination in mod P