組み合わせ:Lucas の定理

競プロのアルゴリズムです。

契機としてはこちら。 atcoder.jp

定理本体の説明や、数学的証明はこちら参照。
manabitimes.jp algo-logic.info

ざっくりいうと、 _{n}C_{k} (mod\ p) を前計算  O(p^{2})、クエリ  O(log_{p}(n)) で計算することができるアルゴリズムです。ただし  p素数

素朴に実装すると、 O(min(n, n-m) \times log(p)) 程度はかかってしまうので  p が小さい場合は極めて高速に計算することができます。

 _{10^{100}}C_{10^{99}} (mod\ 7) とかであれば実用的な速度で計算可能です。 p = 10^{9} + 7 といった、大きめの素数の場合は使えないのでその点はご容赦を。

python スクリプトとしてはこんな感じで。
前処理で逆元を求める必要もないので、その点でも有利ですね。

class LucasTheorem:

    def __init__(self, p): 
        self.p = p
        self.dp = [[0 for j in range(p+1)] for i in range(p+1)]
        # nCk = dp[k][n] なことに注意
        for i in range(p+1): 
            self.dp[0][i] = 1

        for i in range(p):
            for j in range(p):
                self.dp[i+1][j+1] = (self.dp[i][j] + self.dp[i+1][j]) % p

    def get_nCk(self, n, k):
        ans = 1
        while n > 0 or k > 0:
            ans *= self.dp[k % self.p][n % self.p]
            ans %= self.p
            n //= self.p
            k //= self.p
        return ans

使い方はこんな感じ。 _{10^{100}}C_{10^{99}} (mod\ 7) を求めてみます。

lt = LucasTheorem(7)
lt.get_nCk(10 ** 100, 10 ** 99)