卢卡斯定理模板

1.针对p为素数情况：

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #define ed 100005
 5 using namespace std;
 6 int k,n,m,p;
 7 long long a[ed],b[ed];
 8 long long lucas(int x,int y)
 9 {
10     if(x<y) return 0;
11     else if(x<p) return b[x]*a[y]*a[x-y]%p;
12     else return lucas(x/p,y/p)*lucas(x%p,y%p)%p;
13 }
14 int main()
15 {
16     scanf("%d",&k);
17     while(k)
18     {
19         scanf("%d%d%d",&n,&m,&p);
20         a[0]=a[1]=b[0]=b[1]=1;
21         for(int i=2;i<=n+m;i++) b[i]=b[i-1]*i%p;//求阶乘
22         for(int i=2;i<=n+m;i++) a[i]=(p-p/i)*a[p%i]%p;//求逆元
23         for(int i=2;i<=n+m;i++) a[i]=a[i-1]*a[i]%p;//求阶乘的逆元
24         printf("%lld
",lucas(n+m,m));
25         k--;
26     }
27  
28     return 0;
29 }

扩展卢卡斯定理：

  1 #include<bits/stdc++.h> 
  2 #define ll long long
  3 using namespace std;
  4 ll m,n,p;
  5 ll _p[20];
  6 ll e[20];
  7 ll nump[20];
  8 int cnt=0;
  9  
 10 void only(ll n){
 11     for(int i=2;i*i<=n;i++){
 12         if(n%i) continue;
 13         _p[++cnt]=i;
 14         nump[cnt]=1;
 15         while(n%i==0){
 16             n/=i;
 17             e[cnt]++;
 18             nump[cnt]*=i;
 19         }
 20     }
 21     if(n>1) _p[++cnt]=n,e[cnt]=1,nump[cnt]=n;
 22     return ;
 23 }
 24  
 25 ll mypow(ll a,ll b,ll p){
 26     ll ans=1;
 27     while(b){
 28         if(b&1) ans=(ans*a)%p;
 29         a=(a*a)%p;
 30         b>>=1;
 31     }
 32     return ans;
 33 }
 34  
 35 ll exgcd(ll a,ll b,ll &x,ll &y){
 36     if(b==0){
 37         x=1,y=0;
 38         return a;
 39     }
 40     ll d=exgcd(b,a%b,x,y);
 41     ll z=x;
 42     x=y;
 43     y=z-a/b*y;
 44     return d;
 45 }
 46  
 47  
 48 ll cal(ll n,ll p){
 49     ll ans=0;
 50     while(n){
 51         ans+=n/p;
 52         n/=p;
 53     }
 54     return ans;
 55 }
 56  
 57 ll fac(ll n,ll p,ll pk){
 58     if(n==0) return 1;
 59     ll ans=1;
 60  
 61     for(int i=1;i<pk;i++){
 62         if(i%p)
 63             ans=ans*i%pk;
 64     }
 65     ans = mypow(ans,n/pk,pk);
 66  
 67     for(int i=1;i<=n%pk;i++){
 68         if(i%p)
 69             ans=ans*i%pk;
 70     }
 71     return ans*fac(n/p,p,pk)%pk;
 72 }
 73  
 74 ll inv(ll a,ll p){
 75     ll x,y;
 76     ll d=exgcd(a,p,x,y);
 77     return (x%p+p)%p;
 78 }
 79  
 80 ll C(ll n,ll m,ll p,ll pk){
 81     if(n<m) return 0;
 82  
 83     ll facn=fac(n,p,pk),facm=fac(m,p,pk),facn_m=fac(n-m,p,pk);
 84     ll cnt=cal(n,p)-cal(m,p)-cal(n-m,p);
 85     return facn*inv(facm,pk)%pk*inv(facn_m,pk)%pk*mypow(p,cnt,pk)%pk;
 86 }
 87  
 88 ll China(ll n,ll m,ll p){
 89     ll ans=0;
 90     for(int i=1;i<=cnt;i++){
 91         ans=(ans+C(n,m,_p[i],nump[i])*(p/nump[i])%p*inv(p/nump[i],nump[i])%p)%p;
 92     }
 93     return ans;
 94 }
 95  
 96 ll exlucas(ll n,ll m,ll p){
 97     return China(n,m,p);
 98 }
 99  
100 int main(){
101     ll n,m,p;
102     scanf("%lld%lld%lld",&n,&m,&p);//C n m % p
103     only(p);
104     printf("%lld
",exlucas(n,m,p)%p);
105     return 0;
106 }
107