Lucas定理

首先给出关于Lucas定理的简要证明：
定义：
$$ a=a_{k}*p^{k}+a_{k-1}*p^{k-1}+…+a_{1}*p+a_{0}=\sum_{i=1}^{k}a_{i}^p{i} $$
$$ b=b_{k}*p^{k}+b_{k-1}*b^{k-1}+…+b_{1}*p+b_{0}=\sum_{i=1}^{k}b_{i}^p{i} $$
求证：
$$ C_{a}^{b}=C_{a_{k}}^{b_{k}}*C_{a_{k-1}}^{b_{k-1}}…C_{a_{0}}^{b_{0}} $$

首先我们证明引理一：
$$ (1+x)^p≡1+x^p\ (mod\ p) $$
根据组合数基本性质，我们有：
$$\forall j\in [1,p-1],C_{p}^{j}=\frac{p}{j}*C_{p-1}^{j-1}≡0(mod\ p) $$

$$∴(1+x)^p≡\sum_{i=1}^{p}C_{p}^{i}*x^i≡1+x^p(mod\ p) $$
于是我们得到结论：
$$(1+x)^a≡\prod_{i=1}^{k}(1+x)^{p^k*a_{k}}≡\prod_{i=1}^{k}(1+x^{p^{k}})^{a_{k}}(mod\ p)\ (1)$$
根据进制的基本性质和幂的基本性质，我们有：
$$b=\sum_{i=1}^{k}b_{i}^p{i},x^b=\prod_{i=1}^{k}x^{p^k*b_{i}}$$
并且我们知道，用上述方法表示\(p\)进制数，是完全等价的。即，两者的集合构成双射。

故而我们比较\((1)\)式展开后左右各项，可以得到：
$$\forall b\in [1,a],C_{a}^{b}≡\prod_{i=1}^{k}C_{a_{i}}^{b_{i}}(mod\ p)$$

证毕。

故而对于实际处理问题，只需要逆向秦九韶即可。

 

#include<iostream>
#include<cstdio>
using namespace std;
long long n,m,p,inv[100005],fac[100005];
#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B))

//y取x 
inline long long C0(long long x,long long y){
    return ((x>y)?0:(x?fac[y]*inv[x]*inv[y-x]%p:1))%p;
}
//模p意义下的y取x 
inline long long C(long long x,long long y){
    return ((x>y)?0:((y>=p)?C(x/p,y/p)*C0(x%p,y%p):C0(x%p,y%p)))%p;
}
void init(){
    scanf("%lld%lld%lld",&n,&m,&p);
    fac[0]=fac[1]=inv[0]=inv[1]=1;
    for(int i=2;i<=p;++i){
        fac[i]=fac[i-1]*i%p;
        inv[i]=(p-p/i)*inv[p%i]%p;
    }
    for(int i=2;i<=p;++i){
        inv[i]*=inv[i-1];
        inv[i]%=p;
    }
    printf("%lld\n",C(n,n+m)%p);
} 
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        init();
    }
    return 0;
}