每日算法——卢卡斯定理

关键词

给定三个整数 $n, m, p$ , 求 $C_n^{m} \mod p$ 。

$1 \leq m \leq n \leq 10^9, 2 \leq p \leq 10^5$ , 保证 $p$ 为质数。

输出1行，为一个整数，表示答案。

5 2 3

卢卡斯定理：

对于质数 $p$ , 有 $C^n_m \mod p = C^{\lfloor n/p \rfloor}_{\lfloor m/p \rfloor} \cdot C^{n \mod p}_{m\mod p} \mod p$

long long fact(int n) {
    int ans = 1;
    for (int i = 2; i <= n; i++) {
        ans *= i;
    }
    return ans;
}

long long C(int n, int m) {
    return fact(m) / (fact(n) * fact(m-n));
}

long long Lucas(int n, int m, int p) {
    if (m == 0) return 1;
    return (C(n % p, m % p) * Lucas(n / p, m / p, p)) % p;
}