Lucas の定理

$n$ と $r$ を $p$ 進数で表したときの各桁を $n_i$, $r_i$ とすると、 $\binom{n}{r} \equiv \prod_i \binom{n_i}{r_i} \pmod{p}$ が成り立ちます（Lucas の定理）。 $p$ 未満の階乗とその逆元を前計算しておけば、 $n$ や $r$ が $p$ より大きくても求められます。

• Lucas(p): 素数 $p$ を法として前計算。 $O(p)$
• C(n, r): ${}_n\mathrm{C}_r \bmod p$（ $r < 0$ や $r > n$ のときは $0$）。 $O(\log_p n)$

$p$ が $N$ より大きいときは、普通の 二項係数 で十分です。 $p = 2$ のときは、「 ${}_n\mathrm{C}_r$ が奇数になるのは、 $r$ のビットがすべて $n$ のビットに含まれる（(n & r) == r）ときに限る」という形でもよく使います。

コード

class Lucas:
    # 小さい素数 p を法とする二項係数（n, r は大きくてよい）
    def __init__(self, p):
        self.p = p
        self.fact = [1] * p
        for i in range(1, p):
            self.fact[i] = self.fact[i - 1] * i % p
        self.inv = [1] * p
        self.inv[p - 1] = pow(self.fact[p - 1], p - 2, p)
        for i in range(p - 1, 0, -1):
            self.inv[i - 1] = self.inv[i] * i % p

    def C(self, n, r):
        if r < 0 or r > n:
            return 0
        p = self.p
        res = 1
        while n:
            a, b = n % p, r % p
            if b > a:
                return 0
            res = res * self.fact[a] * self.inv[b] * self.inv[a - b] % p
            n //= p
            r //= p
        return res