小さい数を法とする二項係数

$\binom{n}{k} \mod M$を求めたいが、$M$が合成数だったり$k \ge M$だったりして階乗の逆元が得られない場合について。$n$が小さければパスカルの三角形を作ればよいが、$M$が小さい場合にも方法がある。https://discuss.codechef.com/t/your-approach-to-solve-sandwich/14618/13 より。

$M$をいくつかの互いに素な因数に分解してそれぞれを法として二項係数を求めれば、CRTで$\mod M$の値が得られる。したがって、次の問題が解ければよい:

問題: 素数の累乗$p^e$が与えられた時に$\binom{n}{k} \mod p^e$を求めよ。

$f(x, p) :=$ 階乗$x!$を非負整数$e, q$を使って$x! = p^e q$と表す時の最大の$q$

とする。言い換えると、$f(x, p)$は$x!$を$p$で割れる限り割ったものである。$n! = p^{e_1}f(n, p), k! = p^{e_2}f(k, p), (n-k)! = p^{e_3}f(n-k, p)$とするとき、二項係数$\binom{n}{k}$は次のように書ける:

$$\binom{n}{k} = \frac{p^{e_1-e_2-e_3}f(n, p)}{f(k, p)f(n-k, p)}$$

$f(k, p), f(n-k, p)$は$p^e$と互いに素なので$\mod p^e$で逆元を持つ。したがって、$e_1, e_2, e_3$と$f(n, p), f(k, p), f(n-k, p)$が求まれば二項係数を計算できる。

前者、つまり$e_1, e_2, e_3$を求めるほうは簡単で、一般に階乗$x!$が$p$で割れる回数は$\sum_{i=1}^\infty \lfloor x/p^i \rfloor$に等しく（ルジャンドルの公式）、この式で素朴に計算すれば${O}(\log x)$で求まる。

次に$\mod p^e$で$f(x, p)$を計算する問題を考える。$f(x, p)$は$x!$から素因数$p$を除いたものなので、ひとまず階乗から$p$の倍数だけ分離して考えてみる: $X$を$1, 2, ..., x$のうちの$p$の倍数でない数の総積とするとき、$f(x, p) =Xf(\lfloor x/p \rfloor, p)$が成り立ち、${O}(\log x)$回の再帰で$f(0, p)=1$に帰着して$f(x, p)$が求まる。 （実際にはループでよい。）

あとは$X$を$\mod p^e$で求める方法が問題になるが、$p$の倍数の位置は$\mod p^e$で周期的なことを利用できる。最初に「$p$の倍数だけ飛ばした階乗$\mod p^e$」の長さ$p^e$のテーブルを作っておけば、$X$は繰り返し二乗法で${O}(\log x)$で計算できる。

全体の計算量は

• build: ${O}(p^e)$
• query: ${O}((\log n)^2)$

と評価できる。また、冒頭の任意の$M$を法とした二項係数を求める問題に関しては、

• build: ${O}(M)$
• query: ${O}((\log n )^2 \log \log M)$

となる。（$\log \log M$は$M$の異なる素因数の個数の評価。）

---

Lucasの定理の素数の累乗に関する拡張を使う方法もあるらしい。たぶんこちらのほうが速い。 https://arxiv.org/pdf/1301.0252.pdf