用了10个小时,扩展卢卡斯
本来打算用latex写一下,好看点,已经被批评过了,但是我的latex真的太垃圾了,完全找不到大师说的那种行云流水般的感觉。最后,还是拿手写板顺畅的写了一下。
#include <cstdio>
using namespace std;
typedef long long LL;
void exgcd(int a,int b,LL &x,LL &y){
if(b==0){
x=1,y=0;
return;
}
exgcd(b,a%b,y,x);
y-=a/b*x;
}
LL inv(LL a,LL p){
LL x,y;
exgcd(a,p,x,y);
return (x%p+p)%p;
}
LL qmi(LL a,LL b,LL p){
LL res=1%p;
while(b){
if(b&1) res=res*a%p;
b>>=1;
a=a*a%p;
}
return res;
}
LL F(LL n,LL p,LL pk){
if(n==0) return 1;
LL rou=1,rem=1;//循环节,余项
for(LL i=1;i<=pk;i++){
if(i%p) rou=rou*i%pk;
}
rou=qmi(rou,n/pk,pk);
for(LL i=pk*(n/pk);i<=n;i++){
if(i%p) rem=rem*(i%pk)%pk;
}
return F(n/p,p,pk)*rou%pk*rem%pk;
}
LL G(LL n,LL p){
if(n<p) return 0;
return G(n/p,p)+(n/p);
}
LL cpk(LL n,LL m,LL p,LL pk){
LL fz=F(n,p,pk);//分子
LL fm1=inv(F(m,p,pk),pk);//分母1
LL fm2=inv(F(n-m,p,pk),pk);//分母2
LL mi=qmi(p,G(n,p)-G(m,p)-G(n-m,p),pk);//q^{x-y-z}
return fz*fm1%pk*fm2%pk*mi%pk;//返回C(n,m)%p^k
}
LL A[1001],B[1001];//x=B(mod A)
LL exlucas(LL n,LL m,LL p){
LL ljc=p,tot=0;
for(LL i=2;i<=p/i;i++){
if(ljc%i==0){
LL pk=1;
while(ljc%i==0){
pk*=i;
ljc/=i;
}
A[++tot]=pk;
B[tot]=cpk(n,m,i,pk);
}
}
if(ljc!=1){
A[++tot]=ljc;
B[tot]=cpk(n,m,ljc,ljc);
}
LL ans=0;
for(LL i=1;i<=tot;i++){
LL r=p/A[i],t=inv(r,A[i]);
ans=(ans+B[i]*r%p*t%p)%p;
}
return ans;
}
int main(){
LL n,m,p;
scanf("%lld%lld%lld",&n,&m,&p);
printf("%lld\n",exlucas(n,m,p));
return 0;
}
Latex我觉得写着好累的