そのうち誰かの役に立つ

もしくは誰の役にも立たない

素数pを法とする組合せ数

アルゴリズムとデータ構造 nCk mod p Python3 Go

概要

組合せ数 $_n\mathrm{C}_k$ の素数 $p$ による剰余を求める
$_n\mathrm{C}_k = n! \times (n-k)!^{-1} \times k!^{-1}$ なので、それぞれの $p$ による剰余を求めればよい
$0! \equiv 1 (\mathrm{mod} p), k! \equiv (k - 1)! \times k (\mathrm{mod} p)$ と帰納的に求めていくことで $n! \mathrm{mod} p$ を求めることができる
フェルマーの小定理よりなので、両辺をで割るとが言える
- $(k - 1)!^{-1} \equiv k!^{-1} \times k (\mathrm{mod} p)$ であることから残りは帰納的に求められる
もしくは、 $0^{-1} \equiv 1 (\mathrm{mod} p) , 1^{-1} \equiv 1 (\mathrm{mod} p), k^{-1} \equiv p - ((p \mathrm{mod} k)^{-1} \times \lfloor \frac{p}{k} \rfloor) (\mathrm{mod} p)$ により帰納的に $n^{-1}$ が求められるので、そこから $n!^{-1}$ を求める方法もある
これらをメモしておくことで、任意のについてを（前処理を除き）の計算時間で求めることができる
- 前処理の計算時間は $O(n)$ 程度

実装

Comb() 関数は一般化して複数の数を渡すことが可能で、入力 $a_1, \dots , a_k$ について $(\sum_{i=1}^{k}a_i)! \times \prod_{i=1}^{k}(a_i!^{-1})$ を計算している

Python3で実装する

Powered by OnlineGDB

Goで実装する

（筆者の知る限りにおいて）Goの標準ライブラリでは $n!^{p - 2} \mathrm{mod} p$ を高速に計算できないため、 $n^{-1} \mathrm{mod} p$ を計算する手法をとっている