整数 \(n, m\) と素数 \(p\) に対して、以下の関係が成り立つ：

この定理は、\(n\) や \(m\) が非常に大きく、通常の逆元計算（フェルマーの小定理など）が使えない場合に特に有効である。たとえば、\(m\) が \(p\) の倍数だと逆元が存在せず、直接計算できないが、ルーカスの定理を使えば再帰的に小さな部分問題に分解できる。

アルゴリズムの流れ

1. まず、\( \binom{n \bmod p}{m \bmod p} \) を計算。この値は \(p\) より小さいので、階乗と逆元で直接求める。
2. 次に、\( \binom{\lfloor n/p \rfloor}{\lfloor m/p \rfloor} \) を再帰的に計算。
3. 両者の積を \(p\) で割った余りを返す。

基本実装例（P3807 対応）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll mod, fact[100010];

void build_factorials() {
    fact[0] = 1;
    for (int i = 1; i <= 100000; ++i)
        fact[i] = fact[i-1] * i % mod;
}

ll pow_mod(ll base, ll exp) {
    ll res = 1;
    while (exp) {
        if (exp & 1) res = res * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return res;
}

ll comb_small(ll a, ll b) {
    if (a < b || b < 0) return 0;
    ll res = fact[a];
    res = res * pow_mod(fact[a - b], mod - 2) % mod;
    res = res * pow_mod(fact[b], mod - 2) % mod;
    return res;
}

ll lucas(ll n, ll k) {
    if (k == 0) return 1;
    return comb_small(n % mod, k % mod) * lucas(n / mod, k / mod) % mod;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        ll n, m;
        cin >> n >> m >> mod;
        build_factorials();
        cout << lucas(n + m, m) << '\n';
    }
    return 0;
}

POJ 3219: 二項係数の偶奇判定

素数 \(p=2\) でのルーカス定理を適用すると、各ビットごとに \( \binom{n_i}{m_i} \) を評価する。可能な値は以下の4通りのみ：

• \( \binom{0}{0} = 1 \)
• \( \binom{0}{1} = 0 \)
• \( \binom{1}{0} = 1 \)
• \( \binom{1}{1} = 1 \)

つまり、\(n\) の2進数表現のある桁で 0 なのに \(m\) が 1 ならば全体が 0（偶数）。そうでなければ 1（奇数）。これはビット演算で高速に判定可能：

#include <iostream>
using namespace std;

int main() {
    ll n, m;
    while (cin >> n >> m) {
        cout << (((n - m) & m) ? 0 : 1) << '\n';
    }
    return 0;
}

HDU 3304: p進数での桁ごとの自由度

各桁で \(m_i \leq n_i\) ならその桁の選び方は \(n_i + 1\) 通り。全桁の積が答えになる：

#include <cstdio>
int main() {
    int p, n, cas = 1;
    while (scanf("%d %d", &p, &n), p || n) {
        ll ans = 1;
        while (n) {
            ans = ans * (n % p + 1) % 10000;
            n /= p;
        }
        printf("Case %d: %04lld\n", cas++, ans);
    }
    return 0;
}

HDU 3037: 板分け問題への応用

松の実を最大 \(m\) 個分配する方法は、次の式で表される：

これはパスカルの三角形の性質を利用して簡略化できる。最終的に単一の二項係数として計算可能：

// 上記のlucas()関数とbuild_factorials()を流用
int main() {
    int T;
    cin >> T;
    while (T--) {
        ll n, m;
        cin >> n >> m >> mod;
        build_factorials();
        cout << lucas(n + m, m) << '\n';
    }
    return 0;
}

HDU 5226: 行列範囲内の二項係数和

特定の矩形領域内での二項係数の総和を求める。各列について累積和の差分を利用し、ルーカスの定理で個別に計算：

int main() {
    fact[0] = 1;
    ll a, b, c, d;
    while (cin >> a >> b >> c >> d >> mod) {
        if (mod == 1) { cout << "0\n"; continue; }
        build_factorials();
        ll total = 0;
        for (ll col = b; col <= d; ++col) {
            total = (total + lucas(c + 1, col + 1) - lucas(a, col + 1) + mod) % mod;
        }
        cout << total << '\n';
    }
    return 0;
}