lucas定理

模板题

我们知道当 p 为素数且 p>n 时 C(n,m) 的求法，直接求 n!，m! 的逆元, (n-m)! 的逆元，三者相乘取模就是答案。

那么如果 p<=n 时，这个方法就不行了

这时要用到 lucas 定理：

lucas(n,m)就是C(n,m)：

lucas(n,m)=lucas(n/p,m/p)*C(n%p,m%p)%p

边界条件：m==0，lucas(n,m)=1

当然在 C(n,m) 中，当 m>n 时，C(n,m)=0

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 200010
using namespace std;
typedef long long LL;
int T;
LL n,m,p;
LL fac[MAXN];

LL qpow(LL x,LL k){
    LL res=1;
    while(k){
        if(k&1) res=res*x%p;
        x=x*x%p;
        k>>=1;
    }
    return res;
}

LL C(int n,int m){
    if(m>n) return 0;
    return fac[n]*qpow(fac[m],p-2)%p*qpow(fac[n-m],p-2)%p;
}

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

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