mod Pでの組み合わせ

組み合わせ(二項係数) ${}_n{C}_k=C(n,k)=\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\frac{n!}{k!(n-k)!}$ を大きな数n, kについて求めたいとする。

mod Pでの値で良いとする

• それが求まれば複数の値から中国剰余定理で元の値が復元できるから

剰余を取った後で普通の割り算を行うことはできない。 そこでmod Pでの逆元を計算して掛ける。

• 単発での計算なら対数オーダーで逆元を作成
• 大量に計算するなら逆元テーブルを作れば一つ当たりは定数オーダーになる
  • 剰余群逆元漸化式の導出
• 二項係数テーブル

巨大なnについての二項係数