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

题目地址：

题意：求C(n,m)%p的值(1 <= m <= n <= 10^9, m <= 10^4, m < p < 10^9, p是素数)。 思路： 对于和并且p是素数，我们一般采用Lucas定理来解。 1).Lucas定理是用来求 C(n,m) mod p的值,p是素数。其描述为： 如果 那么得到 即 Lucas(n,m,p)=C(n%p,m%p)* Lucas(n/p,m/p,p) Lucas(n,0,p)=1; 2).对于大组合数求模C(N,M)%P=N! / (M! * (N-M)! ) % mod =( N-M+i )! / M!*(i>=1&&i<=M)。然后根据乘法逆元将除法变成乘法即可。

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include