ARC156の解説で、初歩的だが組み合わせの計算がよくわからなかったので、それを理解するためのメモ。
以下のプログラムで、\(\ _n C _r \) が求められる意味がわからない。
MOD = 998244353
table_len = 5 * 10**5
fac = [1, 1]
inv = [1, 1]
finv = [1, 1]
for i in range(2, table_len):
fac.append(fac[-1] * i % MOD)
inv.append(-inv[MOD % i] * (MOD // i) % MOD)
finv.append(finv[-1] * inv[-1] % MOD)
def binom(n, r):
return fac[n] * finv[n - r] % MOD * finv[r] % MOD
print(binom(6,4)) #15\(\ fac \) は factorial で階乗を、\(\ inv \)は inverse で逆元を、\(\ finv \) は factorial inverse で逆元の階乗を事前計算している。
逆元ってなんだ、ってレベルの人間なんだが、そもそも \(\ _n C _r \) の計算方法を思い出そう。
\(\ n \) 個 から \(\ r \) 個を選ぶときの組み合わせは \(\ _n C _r \) とか \(\ \left( \begin{matrix} n\\ r \\ \end{matrix} \right) \) と書いたりする。
通常の算数では、 \(\ _n C _r = \frac{n!}{(n-r)!r!} = \frac{n \cdot (n-1) \cdot (n-2) \cdots 1}{r \cdot (r-1) \cdots 1 \cdot (n-r) \cdot (n-r-1) \cdots 1} = \frac{n \cdot (n-1) \cdot (n-2) \cdots (n-r+1) }{r \cdot (r-1) \cdots 1}\) とかやって計算する。
例えば、上記の計算例のように、「6個から4個を選ぶ」場合、「6個から選ばない2個を選ぶ」のと同意であるため、\(\ _6 C _4 = {_6C _2} = \frac{6 \cdot 5}{2 \cdot 1} = 15 \)として求める。
で、\(\ _6 C _4 \) 位ならいいのだが、数が大きくなったときに、この \(\ _n C _r = \frac{n!}{(n-r)!r!} \) の除算の部分、つまり分母部分が邪魔というか扱いたくないのである。
理由としては、そもそも割り算自体コンピュータ上で比較的遅い処理であるということ。（除算は加算の10倍以上時間がかかる）そしてMOD計算をする場合、除算を完了してからでないとMODを取れない。逆に言えばすべて単純な掛け算の形であれば、計算途中でいくらでもMODを取ることができる。
そこで、割り算を掛け算に変換できたらいいなぁということで、逆元というものを使う。
逆元の求め方として、フェルマーの小定理と拡張ユークリッドを用いたものがあるのだが、フェルマーの小定理の方が理解しやすいのでそちらをまずは見ていく。
素数 \(\ p \) と互いに素の整数 \(\ a \) は、フェルマーの小定理で以下のような関係をもつ。ちなみに、超初歩的だが、\(\ \equiv \) は合同を意味して、両辺の値を \(\ p \) で割ったときのあまりが一致することを意味する。
$$ {a^{p-1} \equiv 1} \left( \text{mod} \quad p \right) \tag{1}$$
この合同の双方を \(\ a \) で割ると、
$$ a^{p-2} \equiv \frac{1}{a} \left( mod \quad p \right) \tag{1}$$
つまり、\(\ a \) で割り算をして \(\ p \) で剰余を取りたいとき、\(\ a \)を \(\ p-2 \) 乗してから \(\ p \) で剰余を取るときの値は一緒ということになる。なので、\(\ a^{-1} \) の逆元は \(\ a^{p-2} \)として求まる。 \(\ p = 7 \) \(\ a =2 \)とかで試してみると良い。
もう一つの方法としてユークリッドの互除法を使ったものがあり、今回もそれを用いている。フェルマーの小定理を使うよりもこちらの方が高速らしい。こちらは以下のページを見てほしい。
for i in range(2, table_len):
fac.append(fac[-1] * i % MOD)
inv.append(-inv[MOD % i] * (MOD // i) % MOD)
finv.append(finv[-1] * inv[-1] % MOD)階乗を求めるに大きな計算を要するので事前に階乗、階乗の逆元、逆元の階乗を計算してテーブルとして保存する。
def binom(n, r):
return fac[n] * finv[n - r] % MOD * finv[r] % MODbinomの部分では、\(\ \frac{n!}{(n-r)!r!} \) の計算したくない分母部分である \(\ (n-r)! \) と \(\ r! \) を逆元にすることで、掛け算の形へと変換する。掛け算にしちゃえば途中でMODを取っても良いのでそのように計算されている。
正直人に説明できるくらい理解できたかと言われると、否ではあるが、雰囲気はとりあえず掴むことができたので一旦退散。。