卢卡斯定理

Lucas 定理

Lucas定理主要用于模数为质数的大组合数的计算，其内容为

Note

\[\binom{n}{m} \equiv \binom{n \mod p}{m \mod p} \times \binom{\left\lfloor n/p\right\rfloor }{\left\lfloor m/p\right\rfloor } \pmod{p}\]

因此我们可以递归求解组合数，代码如下：

P3807 【模板】卢卡斯定理/Lucas 定理

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 10;
ll frac[MAXN], p;
ll qpow(ll a, ll b)
{
    ll res = 1;
    for (; b; b >>= 1, a = a * a % p)
        if (b & 1)
            res = res * a % p;
    return res;
}
ll c(ll n, ll m)
{
    if (m > n)
        return 0;
    return frac[n] * qpow(frac[n - m], p - 2) % p * qpow(frac[m], p - 2) % p;
}
ll lucas(ll n, ll m)
{
    if (!m)
        return 1;
    return lucas(n / p, m / p) * c(n % p, m % p) % p;
}
ll solve()
{
    ll n, m;
    cin >> n >> m >> p;
    n += m;
    for (int i = 1; i <= p; i++)
        frac[i] = frac[i - 1] * i % p;
    return lucas(n, m);
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    frac[0] = 1;
    int T;
    cin >> T;
    while (T--)
        cout << solve() << endl;
    return 0;
}