Saving Beans (卢卡斯定理)

题意：计算在n棵树上采摘不超过m个豆子的可行方案数目

为简化计算，可以额外引入一棵树，当这棵新增的树采摘k个豆子时，原先n棵树所采摘的豆子总数即为m-k，从而满足题设条件，并使问题更易于处理。

此时题目转化为求a1+a2+a3+a4……+an+an+1=m；共有多少组解？

进一步地，将问题转换为求a1+a2+……+an+an+1=m+n+1；共有多少组解？

将第一式中的每个ai都加一后即可得到第二式。

针对第二式的求解：

设想有m+n+1个豆子排成一行，则它们之间恰好存在m+n个空隙。若从这m+n个空隙中选取n个位置插入木板，则这些豆子会被划分为n+1段，每段的数量对应于各个ai的值，即构成第二式的一个解。因此，在m+n个空隙中选取n个位置的问题就转化为组合数的计算。若p≤10^5且为质数，则可采用Lucas定理进行求解。

Lucas定理定义如下：

Lucas(n,m,p)=cm(n%p,m%p,p)*Lucas(n/p,m/p,p);

其中Lucas(x,0,p)=1；

cm(a,b)=a!/(b!*(a-b)!))；

实际上该公式等价于计算 a!/(a-b)!(b!)(p-2) mod p。

 上面这一步变换是根据费马小定理：假如p是质数，且a,p互质，那么a的（p-1）次方除以p的余数恒为1,

    
 那么a和a^(p-2)互为乘法逆