フェルマーの小定理を用いてコンビネーションを計算する

背景

nCk

nCkを計算したい。(n個の中からkこ取り出す組み合わせ)

nCkはnCk = n! / k! * (n - k)!となる。これを計算すれば求まる。しかし、分母のk! * (n - k)!の部分に着目した時に、nの値が大きいと値が大きすぎて計算できない。

そこで、プロコンの世界ではnCkを10⁹+7で割った余り(mod(10⁹+7))を求めさせるようになっていたりする。これによって解は10⁹+7より大きくなることになることはない。また、k! * (n - k)!は大きすぎるので、それぞれの要素に対してmod(10⁹+7)をしたい。それぞれの要素に対して余り計算ができるのは以下の通りだ。

mod計算

35を3で割った余りを計算したい。35 / 3 = 11余り2となる。これは 35 % 3 => 2と表記できる。35は7 * 5で表される。この時、7 % 3 * 5 % 3 => 2と同値となる。余り計算はどのタイミングで余り計算しても計算結果は変わらない。

フェルマーの小定理

k^n-1 ≡ 1 (mod n)

これを変換していくと

k^-1 ≡ k^n-2 (mod n)

となる。

ここで、nCkを再び見てみる。

nCk = n! / k! * (n-k)! これは、nCk = n! * (k!)^-1 * ((n-k)!)^-1 と書ける。また、今回はnCkをmod(10⁹+7)したいので、MOD = 10⁹+7と置くと

nCk (mod MOD) = n! (mod MOD) * (k!)^MOD-2 * ((n-k)!)^{MOD - 2} と書くことができる。 この事から、1 <= i <= n において全てのi!を求めておけば、nCkをO(1)で取得することができる。

階乗の計算結果を予め用意しておく

1 <= i <= nにおける全てのi!は繰り返し２乗法によってO(log n)で用意することができる。 詳しくは以下を参照。

keita-matsushita.hatenablog.com

フェルマーの小定理を使ったコンビネーション計算

計算量

これはO(log(N!))となる。これはO(logN) < O(log(N!)) < O(NlogN) となり、NlogNより小さい。