[HDOJ3037 Saving Beans]Lucas定理

【题目大意】
求C(n+m,n) % p的值。
保证p是素数。
【算法分析】
师傅说存在一个叫Lucas定理。
他在维基百科上：http://en.wikipedia.org/wiki/Lucas%27_theorem
除了这个Lucas定理以外，还要用到快速幂和另外一个不知名定理：
若b与p互质，则(a/b) = a * b^(p-2) (mod p)。
【其它】算阶乘的时候弄错几次，要开int64，不然会乘到溢出的。
【CODE】
#include #include #include #include using namespace std;
typedef __int64 lld;
lld p;
lld jc[105555];

void init(){
jc[0]=1;
for (lld i=1;i<=p;i++) jc[i]=jc[i-1]*i%p;
}

lld Pow_mod(lld x,lld cf){
if (cf==0) return 1;
lld res=Pow_mod(x,cf/2);
res=res*res%p;
if (cf%2) res=res*x%p;
return res;
}

lld C(lld m,lld n){
if (n>m) return 0;
return jc[m]*Pow_mod(jc[n]*jc[m-n]%p,p-2)%p;
}

lld solve(lld m,lld n){
if (n==0) return 1;
return C(m%p,n%p)*solve(m/p,n/p)%p;
}

int main(){
lld Tc,i,m,n;
cin >> Tc;
for (i=0;i cin >> n >> m >> p;
init();
cout << solve(m+n,n) << "n";
}
return 0;
}