刷数论模板啦。。。

在正事之前发现了一个小知识：组合数有两种书写方式。一种是形如\(C_3^2\)，另一种是形如\(\binom{3}{2}\)。这两者等价。

卢卡斯定理其实也简单的：

\[\binom{m}{n}=\binom{m \mod p}{n \mod p} \times \binom{\lfloor \frac{m}{p} \rfloor }{ \lfloor \frac{n}{p} \rfloor} \mod p\]

这是一种简单的表达式。

lucas定理可以求大\(n,m\)的组合数取模。

这是一种递归的算法。下取整的大部分我们可以再次递归缩小范围求解，而取模的部分我们直接暴力来做。

如何暴力？

组合数的定义式：

\[C_m^n=\frac{m!}{n!(m-n)!}\]

在模意义下我们就没除法了。所以我们就要用到乘法逆元了。

我们先预处理出这些阶乘，然后可以用任意一种方法来求这两个阶乘的逆元。暴力乘上去即可。

代码：

#include
    
     const int maxn = 1000005;#define ll long longll n, m, p;ll frac[maxn];ll pow_mod(ll x, ll y, ll p){    ll ans = 1, base = x % p;    while(y)    {        if(y & 1) ans = ans * base % p;        base = base * base % p;        y >>= 1;    }    return ans % p;}ll inv(ll x, ll p){    return pow_mod(x, p - 2, p) % p;}ll C(ll x, ll y, ll p){    if(x < y) return 0;    return frac[x] * inv(frac[y], p) % p * inv(frac[x - y], p) % p;}ll lucas(ll x, ll y, ll p){    if(y == 0) return 1;    return C(x % p, y % p, p) * lucas(x / p, y / p, p) % p;}int main(){    int T; scanf("%d", &T);    while(T--)    {        scanf("%lld%lld%lld", &n, &m, &p);        frac[0] = 1;        for(int i = 1; i <= p; i++) frac[i] = frac[i - 1] * i % p;        printf("%lld\n", lucas(n + m, n, p));    }    return 0;}