#CP nCk % MODの計算

夏休みもいよいよ後半にさしかかろうというところ、ようやく重い腰を上げて競プロを再開したいと思います。でもたぶん数日でまた飽きて競プロをミュートワードにするかもしれません。

今回はCombination(nCkとかのやつ)のMODをテンプレ化しておこうと思います。特に競プロでありがちなnCk % MOD(だいたい10**9+7)です。
「python combination mod」で検索するといろいろ出てきますが、グローバル変数を用意しなくてはならなかったりしてこれ1つコピペすれば完璧！！みたいなのがなかったので変なところに美意識を発揮しがちなオタク的には許せませんでした。なので1つのクラスをコピペすればいいように書きました。なお、完全に競プロ目的で書いたので汎用性はないです。(一度MODを決めたら後から変更はできません)
理論とかは他のサイト様を参照してください。今回はこちらのサイト様を参考にさせていただきました。

keita-matsushita.hatenablog.com

実装例

class comb():
    MOD = 10**9+7
    factrial = [1] # 階乗を保持
    inverse = [1] # 逆元を保持
    
    @staticmethod
    def calc(n, k): # nCk % MODを計算
        comb.pre(n) # 前処理
        ans = comb.factrial[n]*comb.inverse[k]%comb.MOD*comb.inverse[n-k]%comb.MOD
        return ans
    
    @staticmethod
    def pre(n):
        if n <= len(comb.factrial)-1: # nまで計算済み
            return
        else: # それ以外は要計算
            while len(comb.factrial)-1 != n:
                tmp1 = comb.factrial[-1]*len(comb.factrial)%comb.MOD
                comb.factrial.append(tmp1)
                tmp2 = pow(comb.factrial[-1], comb.MOD-2, comb.MOD)
                comb.inverse.append(tmp2)
            return

使用例
クラス定義部分は省略しています

# 5C2 = 10
print(comb.calc(5,2))

# 10C3 = 120
print(comb.calc(10,3))

実行結果

10
120