組み合わせの数をmodで出力するため備忘録

解こうとした問題は以下。190922現在、自分が低支出したコードはTLEになるケースがあり、完全には解けてはいない。
abc042.contest.atcoder.jp
問題は、あるマス目からマス目までの行き方のパターンを出力せよというもので、「答えをそのまま出力すると数が膨大になるため答えを10^9+7で割ったもので出力せよ」と指示がある。
計算数が少ない場合は工夫をせず、 $\dfrac{nCr}{10^9+7}$ を求めて出力すればよいが、そうではない場合があるということである。

詰まったところ

$nCr$ の計算でn,rが大きくなると計算に時間がかかってしまいTLEとなった。
詳しく言うと $nCr = \dfrac{n!}{(n-r)!r!}$ のn!やr!,(n-r)!が大きくなると計算に時間がかかってしまう。

公式の解説から、注意事項抜粋

予め $x!(mod 10^9+7)$ と $x!^{-1}(mod 10^9+7)$ を計算してテーブルにしておく。
計算にはmodを使用し、計算時はそのオーダーに注意する。
$x!^{-1}(mod 10^9+7)$ はフェルマーの小定理を使用し、その計算には二分累乗法など、高速な手法が必要である。

そもそもmodとは

以下動画による解説が良い。
【高校数学(発展)】合同式①(modとは何か)【整数】 - YouTube
【高校数学(発展)】合同式②(modの利用)【整数】 - YouTube
これにより、 $n!(mod 10^9+7)$ を求めることができる。
プログラムで考えると、modを使うことで以下の利点があると推測する。

modに使用する数以下の数値が出力されるため計算結果にはオーバフローがない*1

$n!^{-1}$ を計算する(フェルマーの小定理と二分累乗法)

次に
フェルマーの小定理によって、
$n!^{-1}≡n^{(10^9+7)-2} (mod 10-9+7)$ で求めることができる。
しかし、 $n^{(10^9+7)-2} (mod 10-9+7)$ は普通にやったら時間がかかる。
そのため、工夫が必要になり、解決の一つに二分累乗法がある。
二分累乗法の方法はネット上にあふれている。
繰り返し２乗法を使ったべき乗計算 - マツシタのお勉強メモ
 二分累乗法による累乗計算プログラミング - swift : R for Radio