lucas定理解决大数组合问题

发布时间：2020-12-14 02:41:49 所属栏目：大数据来源：网络整理

导读：数论Lucas定理是用来求 c(n,m) mod p的值,p是素数（从n取m组合，模上p）。描述为: Lucas(n,m,p)=cm(n%p,m%p)* Lucas(n/p,m/p,p) Lucas(x,p)=1; 而 cm(a,b)=a! * (b!*(a-b)!)^(p-2) mod p 也= (a!/(a-b)!) * (b!)^(p-2)) mod p 这里，其实就是直接求 (a!/(a-

数论Lucas定理是用来求 c(n,m) mod p的值,p是素数（从n取m组合，模上p）。

描述为:

Lucas(n,m,p)=cm(n%p,m%p)* Lucas(n/p,m/p,p)

Lucas(x,p)=1;

而

cm(a,b)=a! * (b!*(a-b)!)^(p-2) mod p

也= (a!/(a-b)!) * (b!)^(p-2)) mod p

这里，其实就是直接求 (a!/(a-b)!) / (b!) mod p

由于 (a/b) mod p = a * b^(p-2) mod p

 
   #include<iostream> 
  
   #include<cstdio> 
  
   #include<cstring> 
  
   #include<cstdlib> 
  
   #include<set> 
  
   #include<vector> 
  
   #include<algorithm> 
  
   #define?ll?long?long? 
  
   using? 
   namespace? 
   std; 
  
   int? 
   n,m; 
  
   const? 
   int? 
   p=10007; 
  
   int? 
   qpow( 
   int? 
   a, 
   int? 
   b) 
  
   { 
  
   ???? 
   int? 
   ans; 
  
   ???? 
   for 
   (ans=1;b;b>>=1,a=a*a%p) 
  
   ???????? 
   if 
   (b&1)ans=ans*a%p; 
  
   ???? 
   return? 
   ans; 
  
   } 
  
   int? 
   getc 
   ( 
   int? 
   n, 
   int? 
   m) 
  
   { 
  
   ???? 
   if 
   (n<m) 
   return? 
   0; 
  
   ???? 
   if 
   (m>n-m)m=n-m; 
  
   ???? 
   ll?s1=1,s2=1; 
  
   ???? 
   for 
   ( 
   int? 
   i=0;i<m;i++) 
  
   ???? 
   { 
  
   ???????? 
   s1=s1*(n-i)%p; 
  
   ???????? 
   s2=s2*(i+1)%p; 
  
   ???? 
   } 
  
   ???? 
   return? 
   s1*qpow(s2,p-2)%p; 
  
   } 
  
   int? 
   lucas( 
   int? 
   n, 
   int? 
   m) 
  
   { 
  
   ???? 
   if 
   (m==0) 
   return? 
   1; 
  
   ???? 
   return? 
   getc 
   (n%p,m%p)*lucas(n/p,m/p)%p; 
  
   } 
  
   int? 
   main() 
  
   { 
  
   ???? 
   scanf 
   ( 
   "%d%d" 
   ,&n,&m); 
  
   ???? 
   printf 
   ( 
   "%dn" 
   ,lucas(n,m)); 
  
   ???? 
   return? 
   0; 
  
   }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!