首页 > 代码库 > hdu 3037 Saving Beans (lucas定理)
hdu 3037 Saving Beans (lucas定理)
考虑加多一颗树，这样的话当加的树放了k(0<=k<=m)个beans时，原本的n颗树上放的beans数量之和就等于m-k（<=m）,满足题目的要求 ，也降低了计算的难度。
则题目要求的是a1+a2+......an+an+1=m（0<=ai<=m,1<=i<=n+1) 式1
解有多少组。
考虑把问题转换成，求a1+a2+......an+an+1=m+n+1（1<=ai<=m+1,1<=i<=n+1) 式2
解有多少组。
因为式1的每组解，对于每个ai，都加上1的话，就是式2的一组解。
对于式2的求解：
考虑有m+n+1个Beans排成一列，则它们中恰好有m+n个间隔，在m+n个间隔中选择n个各插入一块木板，则把这些Beans分成n+1部分，每部分的值对应到每个ai，就是式2的一组解。而在m+n个间隔中选择n个，则是求组合数的问题了，p<=10^5且为质数，则可用Lucas定理求。
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;typedef long long ll;ll n,m,p;ll POW(ll x,ll n,ll p){ ll res=1; while(n){ if(n&1)res=res*x%p; n>>=1; x=x*x%p; } return res;}ll cm(ll n,ll m,ll p){ ll a=1,b=1; while(m){ a=a*n%p; b=b*m%p; n--; m--; } return a*POW(b,p-2,p)%p;}ll lucas(ll n,ll m,ll p){ if(!m)return 1; return cm(n%p,m%p,p)*lucas(n/p,m/p,p)%p;}int main(){// freopen("in","r",stdin); int T; cin>>T; while(T--){ scanf("%I64d%I64d%I64d",&n,&m,&p); printf("%I64d\n",lucas(n+m,n,p)); } return 0;}
hdu 3037 Saving Beans (lucas定理)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。