2.1.1. 階乗¶

Code: factorial.py

Test: test_factorial.py

階乗とは¶

Factorial (Wikipedia)

整数 \(n\) について、\(1\) 以上 \(n\) 以下のすべての整数の積をとったもの。 \(n!\) と表記する。

\[n! = n \times (n-1) \times (n-2) \times \ldots \times 2 \times 1\]

\(n\) が小さくても大きな値になりやすく、例えば \(10! = 3628800\) である。

\(n!\) を実際に求めるときは、次式のように再帰的に計算すればよい。

\[\begin{split}\begin{cases} 0! = 1 \\ n! = (n-1)! \times n \quad (n \geq 1) \end{cases}\end{split}\]

階乗の剰余¶

Wilson’s theorem (Wikipedia)

競技プログラミングにおいては \(n < p\) となる素数 \(p\) を法とする剰余を扱うことが多い。
素数を法とするのは \(n!\) が様々な素因数を含むため、合成数で剰余をとると \(0\) になりやすいためである。
また、法が素数でも \(p! \equiv 0\) より、 \(n \geq p\) の範囲で剰余は \(0\) となる。

なお、階乗の剰余については、次のウィルソンの定理が成り立つ。

実用的ではないが、素数であることの証明にも使える。

\[\begin{split}\begin{eqnarray} && (n-1)! \equiv -1 \bmod n \\ &\Leftrightarrow& n \ \text{is a prime number} \end{eqnarray}\end{split}\]

階乗の逆数¶

階乗の剰余が \(0\) でなければ、その逆数が定義される。

素数の法 \(p\) のもとでは \(n < p\) の条件下で逆数が定義される。

階乗の逆数は順列の計算などで、分母に現れる階乗を計算するために利用する。

実装¶

概要¶

素数の法 \(p\) のもとで、 \([1, n] \quad (n < p)\) に対する階乗 \(n!\) とその逆数 \((n!)^{-1}\) を求める。

実装のポイント¶

逆数については最初に \(n!\) の逆数を求めることで、それ以外の逆数は次式を用いて再帰的に求められる。

\[((n-1)!)^{-1} = (n!)^{-1} \times n \quad (n \geq 1)\]

計算量¶

list_mod_facts(n, p) \(\mathcal{O}(n)\)
list_mod_inv_facts(n, p) \(\mathcal{O}(n + \log{n})\)

コード¶

[1]:

from __future__ import annotations


def list_mod_facts(n: int, p: int) -> list[int]:
    f = [1 for i in range(n+1)]
    for i in range(2, n+1):
        f[i] = f[i-1] * i % p
    return f


def list_mod_inv_facts(n: int, p: int) -> list[int]:
    invf = [1 for i in range(n+1)]
    fn = 1
    for i in range(2, n+1):
        fn = fn * i % p
    invf[n] = pow(fn, p-2, p)
    for i in range(n, 2, -1):
        invf[i-1] = invf[i] * i % p
    return invf

使用例¶

[2]:

f = list_mod_facts(10, 997)
print(*f[:11])

1 1 2 6 24 120 720 55 440 969 717

[3]:

invf = list_mod_inv_facts(10, 997)
print(*invf[:11])

1 1 499 831 457 889 979 852 605 178 616