先说下lucas定理
1）Lucas定理：p为素数，则有:
（2）证明： n=(ak...a2,a1,a0)p = (ak...a2,a1)p*p + a0 = [n/p]*p+a0 （注意 这里（）p表示的是p进制数），m=[m/p]*p+b0其次，我们知道，对任意质数p有(1+x)^p=1+(x^p)(mod p) 。我们只要证明这个式子：C(n,m)=C([n/p],[m/p]) * C(a0,b0)(mod p)，那么就可以用归纳法证明整个定理。对于模p而言，我们有下面的式子成立：
上式左右两边的x的某项x^m(m<=n)的系数对模p同余。其中左边的x^m的系数是 C(n,m)。 而由于a0和b0都小于p，因此右边的x^m 一定是由 x^([m/p]*p) 和 x^b0 (即i=[m/p] , j=b0 ) 相乘而得 因此有：C(n,m)=C([n/p],[m/p]) * C(a0,b0) (mod p)。
简化之后就有lu(n,m,p)=c(n%p,m%p,p)*lu(n/p,m/p,p)%p;
通过这个定理我们可以把c（n,m）的数量级降低，然后在计算组合数的时候，如果c（n,m）的值还是很大，我们可以用唯一分解定理来递推。
在计算c(n,m,p)的过程中，记得合理使用同余定理，这里由于有除数还要用到逆元。
http://acm.hdu.edu.cn/showproblem.php?pid=3037
题意：对于m个豆子，我们要存放在n颗树里，问有多少中存放方式。
题解：由于没有规定一定要把豆子全都放在树里，也就是说可能存在剩余的豆子。我们假设剩余的豆子在第n+1颗树上，用x(n)表示第n颗树上的豆子数量。那么就有 x(1)+x(2)+....x(n)+x(n+1)=m。我们左右两边都加上n+1个1那么就有x(1)+1+x(2)+1+....x(n+1)+1=m+n+1;这个等式的求解我们可以理解为从长度为n+m+1的绳子中切出n+1段来，典型的插板法（插板法的简单介绍https://wenku.baidu.com/view/7300b5745acfa1c7aa00cc5f.html），那么问题很明确了 就是求c(n+m,n)模p。
（假设一线段的最小单位为1，我们相把长度为n的线段划分为m段，那么我们可供划分的位置有n-1，需要在这些位置中选m-1个位置做处理所以结果为c(n-1,m-1)---- 插板法）
// x1+x2+x3+x4+x5+...xn=z 的整数解的个数 这里得注意巧用插板法来解决问题
ac代码：
#include <cstdio> #include <iostream> #include <queue> #include <algorithm> using namespace std; typedef long long int ll; ll n,m,p; ll exgcd(ll a,ll b,ll &x,ll &y) { if(b==0) { x=1; y=0; return a; } ll temp=exgcd(b,a%b,y,x); y-=(a/b)*x;// return temp; } ll inv(ll b,ll p)// 求逆元 { ll x,y; ll temp=exgcd(b,p,x,y); if(x < 0) x+=(p/temp); return x; } ll c(ll n,ll m,ll p) { ll a,b; a=b=1; if(m > n) return 0; while(m) { a=(a*n)%p; b=(b*m)%p; n--; m--; } return (ll)a*inv(b,p)%p; } ll lucas(ll n,ll m,ll p) { if(m==0) return 1; return (ll)lucas(n/p,m/p,p)*(ll)c(n%p,m%p,p)%p; } int main() { int t; cin>>t; while(t--) { cin>>n>>m>>p; cout<<lucas(n+m,n,p)<<endl; } return 0; }