浅谈Lucas定理

先占坑。

1. 定义

   若$p\in\mathbb{P},m,n\le p,m,n\in \mathbb{N_*}$，则$C_{m}^{n }\equiv C_\frac mp^\frac np\times C^{n\bmod p}_{m\bmod p}\pmod p$

2. 计算方法

   可以递归$C_\frac mp^\frac np$，递归边界为上下两者小于$p$。

   然后就是快速求$C_m^n$。

   $C_m^n=\frac{m!}{(m-n)!n!}=\frac{m\times (m-1)\times(m-2)\times\cdots\times (m-n+1)\times (m-n)\times\cdots\times 1}{(m-n)\times (m-n-1)\times\cdots\times1\times n!}=\frac{\prod_{i=0}^{n-1} m-i}{n!}$

   这坨子东西下面要逆元，有$n$项；而上面的东西有$n$项。

   所以这两坨子东西可以放一起算，而逆元时间复杂度为$O(\log p)$。

   这样一次的复杂度为$O(n\log p)$。

3. 快速算的代码

#include<bits/stdc++.h>
#define ns "-1"
#define fs(i,x,y,z) for(ll i=x;i<=y;i+=z)
#define ft(i,x,y,z) for(ll i=x;i>=y;i+=z)
#define ll long long
#define ull unsigned long long
#define db double
#define ms(a,b) memset(a,b,sizeof(a))
#define sz(a) sizeof(a)
using namespace std;
const int rw[]={-1,0,1,0,-1,1,-1,1},cl[]={0,1,0,-1,-1,1,1,-1};
const int N=100001,inf=0x7f7f7f7f;
const int daynum[]={114514,31,28,31,30,31,30,31,31,30,31,30,31};
const db E=2.718281828459,pi=acos(-1.0),eps=0.0000000001;
inline ll read(){
	ll date=0,w=1;char c=0;
	while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
	while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
	return date*w;
}
ll ksm(ll a,ll b,ll p){
    ll ans=1%p,base=a;
    while(b){
        if(b&1){
            ans*=base;ans%=p;
	    }
	    base*=base;base%=p;
	    b>>=1;
	}
    return ans%p;
}
ll ck(ll a,ll b,ll p){
    ll res=1,j=a;
    fs(i,1,b,1){
        res=res*j%p;
        res=res*ksm(i,p-2,p)%p;
        j--;
    }
    return res%p;
}
ll lucas(ll a,ll b,ll p){
    if(a<p&&b<p) return ck(a,b,p);
    return ck(a%p,b%p,p)*lucas(a/p,b/p,p)%p;
}
int t;
int main(){
    t=read();
    while(t--){
        ll a,b,p;a=read(),b=read(),p=read();
        printf("%lld\n",lucas(a+b,b,p));
    }
    return 0;
}