HDU 3037 组合数、lucas，逆元

题目大意，N颗树上取不超过M个果子，求总方案个数模P的值，P是质数且不超过10w，N,M不超过1e9；

在这里树是被认为不同的，也就是将k(0<=k<=M)个小球放入N个不同的盒子的方案个数，这是一个经典的问题-->

< n个相同球放入m个不同盒，盒子可空，方案数C(n+m-1,m-1) >

所以答案就是求 SUM{C(N+i-1,i) | 0<=i<=M},这个式子可以利用 C(n,k)=C(n-1,k)+C(n-1,k-1)来化简，因为第一项C(N-1,0)==C(N,0),过程略;

化简之后就是 C(N+M,M),利用lucas求解即可。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define LL long long
 4 LL f[100005]={1};
 5 LL qpow(LL a,LL n,LL p)
 6 {
 7     LL ret=1;
 8     for(;n;n>>=1,a=a*a%p) if(n&1) ret=ret*a%p;
 9     return ret;
10 }
11 void inif(LL P)
12 {
13     for(LL i=1;i<=P;++i) f[i]=i*f[i-1]%P;
14 }
15 LL lucas(LL N,LL M,LL P)
16 {
17     LL ret=1;
18     while(N&&M){
19         LL _N=N%P,_M=M%P;
20         if(_N<_M) return 0;
21         ret=ret*f[_N]%P*qpow(f[_M]*f[_N-_M]%P,P-2,P)%P;
22         N/=P;
23         M/=P;
24     }
25     return ret;
26 }
27 int main()
28 {
29     LL N,M,P,T;
30     cin>>T;
31     while(T--){
32         cin>>N>>M>>P;
33         inif(P);
34         cout<<lucas(N+M,M,P)<<endl;
35     }
36     return 0;
37 }