前言

最近刷模板题，然后刷到了卢卡斯定理，AK了就来写了。

阅读本文你需要的知识

组合计数，MOD运算

正文

卢卡斯定理用于求解大组合数取模的问题，正常的组合数通过递推或者公式计算出，但大组合数会很慢。但当问题规模很大，而模数是一个不大的质数的时候，就不能简单地通过递推求解来得到答案，所以我们的前辈们就发明(发现)了卢卡斯定理，方便我们解决此类毒瘤问题。
卢卡斯定理的定义式如下：
C(m, n) mod p = C(int(m / p), int(n / p)) × C(m mod p, n mod p) mod p
其中int为向下取整，p为质数。
因为 m mod p 和 n mod p 一定比p小，所以可以直接求解C(m mod p, n mod p).
而剩下的C(int(m / p), int(n / p))则继续用卢卡斯定理递归求解。

C语言实现：

#include <stdio.h>

typedef long long ll;

ll a[100010];

ll dpow(ll y, int z, int p) {
    y %= p;
    ll ans = 1;
    for(int i = z; i; i >>= 1 , y = y*y%p)
        if(i & 1)
            ans = ans * y % p;
    return ans;
}

ll C(ll n, ll m, int p) {
    if(m > n)
        return 0;
    return ((a[n] * dpow(a[m], p - 2, p)) % p * dpow(a[n - m], p - 2, p) % p);
}

ll lucas(ll n, ll m, ll p) {
  if (m == 0) 
    return 1;
  return (C(n % p, m % p, p) * lucas(n / p, m / p, p)) % p;
}

int main() {
    int T;
    ll n, m, p;
    scanf("%d", &T);
    while (T--) {
        scanf("%lld %lld %lld", &n, &m, &p);
        a[0] = 1;
        for(int i = 1; i <= p; ++i)
            a[i] = (a[i - 1] * i) % p;
        printf("%lld\n", lucas(n + m, n, p));
    }
    return 0;
}