已知 \(n,m,P\)，求 \(\binom{n}{m} \mod P\)。
与普通 Lucas 不同的是 \(p\) 不一定是质数。
先考虑把 \(P\) 拆成 \(p_1^{k_1}p_2^{k_2}...\) 形式，这样只需要对每个 \(p_i^{k_i}\) 求解后用中国剩余定理合并就好了。
所以求 \(\binom{n}{m} \mod p_i^{k_i}\)。
不能直接求逆元，因为 \(m!\) 可能是 \(p_i\) 的倍数，找不到逆元。
所以需要把上下的 \(p_i\) 除掉，变成
这样就可以直接做了。
那么咋化成这样呢？
以 \(n!\) 为例。
\(1\times 2\times 3\times ...\times n \mod p_i^{k_i}\)
把所有含有 \(p_i\) 的拿出来。
\(p_i^{\left\lfloor \frac{n}{p_i} \right\rfloor}\times (1\times 2\times 3...\times \left\lfloor \frac{n}{p_i} \right\rfloor)\times (1\times 2\times ...\times (p_i-1)\times (p_i+1)...\times n)\mod p_i^{k_i}\)
把后面的化简一下。
\(p_i^{\left\lfloor \frac{n}{p_i} \right\rfloor}\times \left\lfloor \frac{n}{p_i} \right\rfloor! \times (1\times 2\times ...\times (p_i-1)\times (p_i+1)...(p_i^{k_i}-1))^{\left\lfloor \frac{n}{p_i^{k_i}} \right\rfloor}\times (1\times 2\times 3...\times (n\mod p_i^{k_i})) \mod p_i^{k_i}\)。
把后面去掉 \(p_i\) 倍数的阶乘预处理一下，然后就可以递归做了。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int jie[1000005];
int kuai(int a,int b,int mod){
int ans=1;
for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)ans=1ll*a*ans%mod;
return ans;
}
pair<int,int> L(int n,int p,int P){
if(!n)return make_pair(0,1);
pair<int,int> t=L(n/p,p,P);
return make_pair(t.first+n/p,1ll*t.second*kuai(jie[P-1],n/P,P)%P*jie[n%P]%P);
}
void exgcd(int a,int b,int &k,int &x,int &y){
if(b==0){x=1;y=0;k=a;return;}
exgcd(b,a%b,k,y,x);
y-=(a/b*x);
}
int a1,a2,n1,n2,a[1000],np[1000],tot;
void china(){
int d=a2-a1,k,x,y;
exgcd(n1,n2,k,x,y);
x=((x*d/k)%(n2/k)+(n2/k))%(n2/k),a1=x*n1+a1,n1=(n1*n2)/k;
}
int china1(){
a1=a[1],n1=np[1];
for(int i=2;i<=tot;i++){
a2=a[i],n2=np[i];
china();
}
return a1;
}
int n,m,mod;
int phi(int p,int s){
int ans=p-1;
for(int i=2;i<=s;i++)ans=ans*p;
return ans;
}
void work(int i,int P,int s){
jie[0]=1;
for(int j=1;j<=P;j++)if(j%i==0)jie[j]=jie[j-1];else jie[j]=1ll*jie[j-1]*j%P;
pair<int,int> t1=L(n,i,P),t2=L(m,i,P),t3=L(n-m,i,P);
t1.first-=t2.first+t3.first;
int Phi=phi(i,s);
np[++tot]=P,a[tot]=1ll*t1.second*kuai(t2.second,Phi-1,P)%P*kuai(t3.second,Phi-1,P)%P*kuai(i,t1.first,P)%P;
}
signed main(){
scanf("%lld%lld%lld",&n,&m,&mod);
for(int i=2;i*i<=mod;i++){
int s=0,P=1;
while(mod%i==0)mod/=i,s++,P*=i;
if(s)work(i,P,s);
}
if(mod>1)work(mod,mod,1);
printf("%lld",china1());
}