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;
}