DP:フィボナッチ数、階乗、組み合わせ数

タイトルには DP と付けましたが、どちらかというと計算のメモ化の色が強いです。
今回は、あると便利なフィボナッチ数、階乗、組み合わせ数の計算スクリプトをご用意したので記事にいたします。

コンテストに参加していると、ふとした瞬間に「階乗を計算するスクリプトが欲しい!」とか、「 _nC_r 0 \leq r \leq n の範囲全部で計算したい!」みたいになることってないでしょうか。私はよくあります。

必要になってからスクリプトを用意しはじめると、疲れてしまって本題の問題を解く気力がなくなってしまうので、事前に用意しておいて貼り付けられるようにしました。今回はタイトルの通り、フィボナッチ数、階乗とその逆数、組み合わせ数(順列、重複組み合わせ)をご用意しました。是非ご活用ください。

まずはフィボナッチ数を計算するスクリプトです。

class Fibonacci:
    def __init__(self, n, mod=1000000007):
        assert n > 0
        self.n = n
        self._fibonacci = [0 for _ in range(n + 1)]
        self._fibonacci[1] = 1
        for i in range(2, n + 1):
            self._fibonacci[i] = (self._fibonacci[i - 1] + self._fibonacci[i - 2]) % mod

    def get(self, n):
        return self._fibonacci[n]

使い方の例としては、こうです。

def main():
    fib = Fibonacci(100)
    print(fib.get(100))

if __name__ == "__main__":
    main()

Fibonacci クラスをインスタンス化し、get メソッドで取得したいフィボナッチ数列の項数を指定すると、その項の値が返されます。コンストラクタの第一引数には get メソッドで取得する予定の項数の最大値を、キーワード引数 mod には、計算結果が大きくなることがあるので、問題で法が指定されている場合はそれを渡してあげてください。
インスタンス化の際の計算量は  O(n)、値の取得の計算量は  O(1) です。


次は、階乗とその逆数の計算スクリプトです。

class Factorial:
    def __init__(self, n, mod=1000000007):
        self.n = n
        self._factorial = [0 for _ in range(n + 1)]
        self._factorial[0] = 1
        
        for i in range(n):
            self._factorial[i + 1] = (self._factorial[i] * (i + 1)) % mod
    
    def get(self, n):
        return self._factorial[n]


class Factorial_inv:
    def __init__(self, n, mod=1000000007):
        self.n = n
        self._factorial_inv = [0 for _ in range(n + 1)]
        self._factorial_inv[0] = 1
        
        for i in range(n):
            self._factorial_inv[i + 1] = (self._factorial_inv[i] * pow(i + 1, -1, mod)) % mod
    
    def get(self, n):
        return self._factorial_inv[n]

使い方や仕組みはフィボナッチ数とほぼ同じなので割愛です。もしかすると pow(i, -1, mod) をご存じない方もいるかもなのでご説明すると、python で pow(a, -1, p) を実行すると  a \times b  \equiv 1 \ (mod \  p) を満たす  b が返されます。第二引数が負数の場合、第三引数は素数である必要があります。詳しくはリンク先をどうぞ。
この pow(a, -1, p) の計算には計算量  O(log(p)) かかります。そのため、こちらの階乗計算スクリプトは、通常版はインスタンス化の際の計算量が  O(n)、値の取得の計算量は  O(1) となり、逆数版はインスタンス化の際の計算量が  O(n\ log(mod))、値の取得の計算量は  O(1) となります。


最後に、順列と重複組み合わせのスクリプトです。

class nPr:
    def __init__(self, n, mod=1000000007):
        self.n = n
        self._nPr = [0 for _ in range(n + 1)]
        self._nPr[0] = 1
        for i in range(n):
            self._nPr[i + 1] = (self._nPr[i] * (n - i)) % mod
    
    def get(self, r):
        return self._nPr[r]


class nCr:
    def __init__(self, n, mod=1000000007):
        self.n = n
        self._nCr = [0 for _ in range(n + 1)]
        self._nCr[0] = 1
        for i in range(n):
            self._nCr[i + 1] = (self._nCr[i] * (n - i) * pow(i + 1, -1, mod)) % mod
    
    def get(self, r):
        return self._nCr[r]

使い方はフィボナッチ数や階乗の使い方とほぼ同じなので、割愛します。
こちらのスクリプトは、 _nP_r _nC_r n が固定されている場合にお使いください。逆に  n が固定されていない場合や、 _nH_r などを計算する場合は、階乗とその逆数から計算する方がたぶん楽だと思います。
計算量は階乗のときと同じく、pow(i, -1, mod) の計算が入っていない  _nP_r の方はインスタンス化の際の計算量が  O(n)、値の取得の計算量は  O(1) となり、pow(i, -1, mod) の計算が入っている  _nC_r の方はインスタンス化の際の計算量が  O(n\ log(mod))、値の取得の計算量は  O(1) となります。