Как вычислять C(n, k) mod p, когда n и k огромны (теорема Люка)?

Теорема Люка: запиши n и k в системе счисления по основанию p как n = (n_m ... n_1 n_0)_p и k = (k_m ... k_0)_p. Тогда

C(n, k) ≡ ∏ C(n_i, k_i) (mod p),

где все «цифры» n_i, k_i лежат в [0, p-1]. Если хоть в одном разряде k_i > n_i, всё произведение равно 0.

Идея: маленькие C(n_i, k_i) с обоими аргументами < p считаем напрямую (предподсчёт факториалов до p), а большие n,k разбираем поразрядно.

long long power(long long a, long long b, long long p){long long r=1;a%=p;while(b){if(b&1)r=r*a%p;a=a*a%p;b>>=1;}return r;}

long long C_small(long long n, long long k, long long p) {
    if (k > n) return 0;
    long long num = 1, den = 1;
    for (long long i = 0; i < k; i++) {
        num = num * ((n - i) % p) % p;
        den = den * ((i + 1) % p) % p;
    }
    return num * power(den, p - 2, p) % p; // p простое
}

long long lucas(long long n, long long k, long long p) {
    if (k == 0) return 1;
    return C_small(n % p, k % p, p) * lucas(n / p, k / p, p) % p;
}

Сложность: глубина рекурсии O(log_p n), на каждом шаге C_small за O(p log p). Итого O(p · log_p(n) · log p). Работает только для простого p.