hdu 3944 Lucas定理--大组合数取模多校赛

只需两步：1、从杨辉三角推公式，汗一下，高中会这个，但是大学只学了高数没学组合数学，于是呵呵了~~~~不会推导的话，看看这个http://blog.csdn.net/xieshimao/article/details/6699805

2、再谈Lucas定理，看我的另一篇博客吧（随后奉上），

3、对于fac[i][j] 意思是的（j-1）！%p，这个需要预先处理出来，否则果断TLE

我写这个题的时候，还不懂lucas定理，但是想，咱做ACM的，至少会套模板吧，所以用了lucas的模板，然后AC掉了，，以后也是这样吧，如果理解不了算法，至少要会用，直接放弃题目，一点收获也没有啊，至少用模版的时候我自己做的，没参考题解

贴代码

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         using namespace std; #define ll long long const int MAXN = 10010; const int N = 1e9+100; //筛法求素数 bool is[MAXN];int prm[MAXN],pos[MAXN]; ll fac[1250][10001]; int k; int getprm(int n){ int i,j,k; for(i=0;i
        
         >=1; } return ans; } ll C(ll n, ll m,int p,int tt) { if(m > n) return 0; return fac[tt][n]*pow(fac[tt][m]*fac[tt][n-m], p-2,p) % p; } ll Lucas(ll n, ll m, int p,int tt) { if(m ==0) return 1; else return (C(n%p, m%p,p,tt)*Lucas(n/p, m/p,p,tt))%p; } int main() { ll n,m,p; int cnt=0; Init(); while(~scanf(%I64d%I64d%I64d,&n,&m,&p)) { if(m>n/2) m=n-m;//这里不作处理会wa,应该是溢出？ int tt=pos[p]; printf(Case #%d: %I64d ,++cnt,(Lucas(n+1,m, p,tt)-m+n+p)%p); } return 0; }

hdu 3944 Lucas定理--大组合数取模 多校赛