毎回逆元の計算方法を忘れるので、備忘録として残します。
TLDL;
整数Nの逆元(inverse)の求め方
inv = pow(N, MOD-2, MOD)
上記の計算式が成り立つ理由
フェルマーの小定理を使います。wiki
p を素数とし、a と p は互いに素とするときに、 以下が成り立つ。
a^{p-1}≡1 (mod \ p)
今回 $a^{-1}$ を modで取りたいとした時に、以下のxを求めることを考えます。
a^{-1}≡x (mod \ p)
フェルマーの小定理の両辺に $a^{-1}$ をかけます。
\displaylines{
a^{p-1} \times a^{-1} ≡ a^{-1} (mod \ p) \\
a^{p-2}≡ a^{-1} (mod \ p)
}
上記より、$a^{-1}$ が $a^{p-2}$のmod pで表すことが示せました。
nCrの例題
逆元はnCrを求めるときなどでも非常に役立ちます。
例）${}_{1000}C_9$ $(mod \ p)$ を求める場合 $(p = 10^9+7)$
$1000!$ をまず求めます。
MOD = 10**9 + 7
fact = [1]*(1001)
for i in range(1, 1001):
fact[i] = fact[i-1] * i % MOD
fact[1000]で$1000!$が求まります。
次に$1000!$までの逆元を求めます。
invfact = [1]*(1001)
for i in range(1, 1001):
invfact[i] = pow(fact[i], MOD-2, MOD)
${}_nC_r$は$n! / ((n-r)!*r!)$であるため、答えは以下になります。
ans = fact[1000] * invfact[1000-9] % MOD * invfact[9] % MOD