poj—— 3037 Saving Beans
Saving Beans
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5769 Accepted Submission(s): 2316
Now they turn to you for help, you should give them the answer. The result may be extremely huge; you should output the result modulo p, because squirrels can’t recognize large numbers.
Then followed T lines, each line contains three integers n, m, p, means that squirrels will save no more than m same beans in n different trees, 1 <= n, m <= 1000000000, 1 < p < 100000 and p is guaranteed to be a prime.
1 2 5
2 1 5
3
Hint
For sample 1, squirrels will put no more than 2 beans in one tree. Since trees are different, we can label them as 1, 2 … and so on.
The 3 ways are: put no beans, put 1 bean in tree 1 and put 2 beans in tree 1. For sample 2, the 3 ways are:
put no beans, put 1 bean in tree 1 and put 1 bean in tree 2.
题目可以转换成 x1+x2+……+xn=m 有多少组解,m在题中可以取0~m。
利用插板法可以得出x1+x2+……+xn=m解的个数为C(n+m-1,m);
则题目解的个数可以转换成求 sum=C(n+m-1,0)+C(n+m-1,1)+C(n+m-1,2)……+C(n+m-1,m)
利用公式C(n,r)=C(n-1,r)+C(n-1,r-1) == > sum=C(n+m,m)。
就是要求C(n+m,m)%p。
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define ll long long using namespace std; ll t,n,m,p,ans; ll read() { ll x=,f=; char ch=getchar(); ; ch=getchar();} +ch-'; ch=getchar();} return x*f; } ll qpow(ll n,ll k) { ll res=; while(k) { ) res=res*n%p; n=n*n%p; k>>=; }return res; } ll c(ll n,ll m) { ; ll n1=,m1=; ;i<=n;i++) n1=n1*i%p; ;i<=m;i++) m1=m1*i%p; ); } ll lus(ll n,ll m) { ) ; return c(n%p,m%p)*lus(n/p,m/p)%p; } int main() { t=read(); while(t--) { n=read(),m=read(),p=read(); ans=lus(n+m,m); printf("%lld\n",ans); } ; }
最新文章
- wifi强度数据采集器(android)
- thinkphp多表关联并且分页
- SqlDependency 的使用
- Python学习笔记 :01概述
- Populating Next Right Pointers in Each Node 解答
- 纪中集训 Day 7
- js全选checkbox框
- Linux 定时任务详解
- data-packed volume container - 每天5分钟玩转 Docker 容器技术(43)
- python Mysql 库表
- [JavaScript] AMD和CMD概述
- 计算机网络--差错检测(帧检验序列FCS计算方法)
- ASP.NET MVC计划任务实现方法(定时执行某个功能)
- (转)python logging模块
- react native (一)
- 《图解 HTTP 》阅读 —— 第一章
- 使用java开发微信公众平台(1)
- 使用 puppeteer 创建一个自动化导出 PDF 的服务
- WINSOCK网络函数
- Source Insight 4.0的使用(转)