組み合わせ：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)