1..=N の階乗逆数・ただの逆数を O(N) 時間で前計算する方法（mod p）

$N$ を正整数、$p$ を素数、$N < p$ とし、ともにワードサイズに収まると仮定します。

各方法について、「インクリメンタル: OK/NG」、「割り算: ○回使う/使わない」を記していきます。 $N$ までの前計算ができているときに、定数時間で $N + 1$ までの前計算に伸ばせる時に、「インクリメンタル: OK」です。

方法	インクリメンタル	割り算	要約
1. 階乗逆数	NG	$\log p$ 回以下使う	$N!$ の逆数を取る
2. 逆数	OK	$N$ 回以下使う	ユークリッドの互除法を 1 回で止める
3. 階乗逆数、ふたたび	OK	$N$ 回以下使う	方法 2 の応用
4. 逆数、ふたたび	NG	$\log p$ 回以下使う	方法 1 の応用

1. 階乗逆数

1. $1!, 2!, \dots, N!$ をこの順に掛け算で計算してきます。$(i + 1)! = i! \cdot (i + 1)$ を使いましょう。
2. $N!^{-1}$ をユークリッドの互除法などで計算します。（$O(\log p)$ 時間）
3. $(N - 1)!^{-1}, (N - 2)!^{-1}, \dots, 1^{-1}$ をこの順に掛け算で計算してきます。$i!^{-1}= (i + 1)!^{-1} \cdot (i + 1)$ を使いましょう。

全体で $O(N + \log p)$ 時間です。

2. 逆数

$i^{-1}$ を、$1^{-1}, 2^{-1}, \dots, (i - 1)^{-1}$ を用いて表すことを目指しましょう！

$p$ を $i$ で割った商、あまりをそれぞれ $q, r$ と置きましょう。 すると、$p = iq + r, 0 < r < i$ が成り立ちますね。（割り切れないので $r \neq 0$） これを $\mod p$ すると $0 = iq + r$ となりますね。 さらに以降して $ir$ で割ると、$i^{-1} = -qr^{-1}$ となります。

ところで $0 < r < i$ でしたから、$r^{-1}$ はすでに分かっていましたね。 というわけで、定数時間で $i^{-1}$ が計算できますので、$1^{-1}, 2^{-1}, \dots, N^{-1}$ が合計 $O(N)$ 時間で計算できました。

3. 階乗逆数、ふたたび

1. 方法 2 のように $1^{-1}, 2^{-1}, \dots, N^{-1}$ を前計算します。
2. $1!, 2!, \dots, N!$ をこの順に掛け算で計算してきます。$(i + 1)! = i! \cdot (i + 1)$ を使いましょう。
3. $1!^{-1}, 2!^{-1}, \dots, N!^{-1}$ をこの順に掛け算で計算してきます。$(i + 1)!^{-1} = i!^{-1} \cdot (i + 1)^{-1}$ を使いましょう。

4. 逆数、ふたたび

1. 方法 1 のように $1!^{-1}, 2!^{-1}, \dots, N!^{-1}$ を前計算します。
2. $i^{-1} = i^{-1} \cdot (i - 1)$ により、$1^{-1}, 2^{-1}, \dots, N^{-1}$ を計算します。