#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

#CP テンプレ集 Python

競プロメモ

お久しぶりです、モチベがなかったりモチベがなかったりAP受けてたりモチベがなかったりで更新してませんでした。
f:id:harutech:20190518232023p:plain

pythonで競技プログラミングに使えるテンプレ集みたいなのを作っておこうと思い立ったので作ることにします。

二分探索

def binary_search(key, a, ng, ok):
    while abs(ok-ng) > 1:
        mid = (ok+ng)//2
        if midが条件を満たしているかどうか: ok = mid
        else ng = mid
    return ok

使用例

atcoder.jp

しゃくとり法

for left in range(N):
    while right < N and 右に進める条件:
        # なんらかの処理
        right += 1
    # 毎回の処理
    if left == right:
        # leftがrightに追いついたときの処理(大抵はright += 1 ?)
    else:
        # 追いついてない時の処理(left += 1に伴う処理)

半開区間で[left,right)としています。だからright-leftとすればその区間の要素数になります。条件を満たすl,rの個数を調べたいときはright-leftで計算しましょう。

使用例

atcoder.jp

深さ優先探索

def dfs(v):
    Stack = []
    visit[v] = True
    while Stack:
        v = Stack.pop()
        # vを処理する
        for i in 隣接リスト[v]:
            if not visit[i]:
                visit[i] = True
                Stack.append(i)

使用例

atcoder.jp