過去記事, Python で mod の下での逆元を計算するテーブルを作成する - わかばめにっき では, modの下での階乗の逆元を求めました. 本記事では, 以下の記事を参考にして二項係数 を前処理 , 実行 で行うアルゴリズムを紹介します. drken1215.hatenablog.com

wakabame.hatenablog.com では, の素数 で割った余りを求める方法について解説しました. 実は, この計算アルゴリズムは高速化できます.