数论——lucas定理-白红宇

数论——lucas定理

阅读量：4979 次

发布时间：2019-06-12

本文共 2252 字，大约阅读时间需要 7 分钟。

网上证明很多，虽然没看懂。。。。

主要解决大组合数取模的情况

费马小定理求大组合数：

a^(p-1)=1%p;

两边同除a

a^(p-2)=1/a%p;

C（n,m）= n!/(m!*(n-m)!)

所以C（n,m）=f(n)*qpow(f(m)*f(n-m),MOD-2))%MOD

预处理组合数f

百度之星2016 1003

先推公式，再lucas

p很大的情况 1e9+7

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
            8 #include
            
              9 #include
             
              10 #include
              
               11 #include
               
                12 #include
                
                 13 #define clc(a,b) memset(a,b,sizeof(a))14 #include 
                 
                  15 const int maxn = 20005;16 const int inf=0x3f3f3f3f;17 const double pi=acos(-1);18 typedef long long LL;19 using namespace std;20 const LL MOD = 1e9+7;21 22 LL exp_mod(LL a, LL b, LL p)23 {24 LL res = 1;25 while(b != 0)26 {27 if(b&1) res = (res * a) % p;28 a = (a*a) % p;29 b >>= 1;30 }31 return res;32 }33 34 LL Comb(LL a, LL b, LL p)35 {36 if(a < b) return 0;37 if(a == b) return 1;38 if(b > a - b) b = a - b;39 40 LL ans = 1, ca = 1, cb = 1;41 for(LL i = 0; i < b; ++i)42 {43 ca = (ca * (a - i))%p;44 cb = (cb * (b - i))%p;45 }46 ans = (ca*exp_mod(cb, p - 2, p)) % p;47 return ans;48 }49 50 LL Lucas(int n, int m, int p)51 {52 LL ans = 1;53 54 while(n&&m&&ans)55 {56 ans = (ans*Comb(n%p, m%p, p)) % p;57 n /= p;58 m /= p;59 }60 return ans;61 }62 63 int main()64 {65 int n, m;66 LL p;67 while(~scanf("%d%d", &n, &m))68 {69 p=MOD;70 printf("%I64d\n", Lucas(n+m-4, m-2, p));71 }72 return 0;73 }

p在100000左右

HDU 3037

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
            8 #include
            
              9 #include
             
              10 #include
              
               11 #include
               
                12 #include
                
                 13 #define clc(a,b) memset(a,b,sizeof(a))14 #include 
                 
                  15 const int maxn = 20005;16 const int inf=0x3f3f3f3f;17 const double pi=acos(-1);18 typedef long long LL;19 using namespace std;20 //const LL MOD = 1e9+7;21 22 LL PowMod(LL a,LL b,LL MOD){23 LL ret=1;24 while(b){25 if(b&1) ret=(ret*a)%MOD;26 a=(a*a)%MOD;27 b>>=1;28 }29 return ret;30 }31 LL fac[100005];32 LL Get_Fact(LL p){33 fac[0]=1;34 for(int i=1;i<=p;i++)35 fac[i]=(fac[i-1]*i)%p;36 }37 LL Lucas(LL n,LL m,LL p){38 LL ret=1;39 while(n&&m){40 LL a=n%p,b=m%p;41 if(a