HDU3037 附Lucas简单整理
Saving Beans
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4941 Accepted Submission(s): 1957
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.
题目大意:
由n个不同的盒子,在每个盒子中放一些求(可以不放),使得总球数小雨等于m,求方案数(mod p).
1<=n,m<=10^9,1<p<10^5,保证p是素数
分析:
设最后放了k个球,根据"隔板法"由方案数C(k+n-1,n-1),:
ans=C(n-1,n-1)+C(n,n-1)+C(n+1,n-1)+……+C(n+m-2,n-1)+C(n+m-1,n-1)
=C(n+m,n);(mod p)
由于数据范围很大,C(n,m)=C(n-1,m)+C(n-1,m-1);显然会TLE
最后组合数还要mod p,这时候 Lucas定理 闪亮登场
============================================
Lucas定理(shenben简单总结版)
============================================
Lucas定理1:
Lucas(n,m,p)=cm(n%p,m%p)*Lucas(n/p,m/p,p);{其中cm(a,b)=C(a,b)%p;Lucas(x,0,p)=1;}
Lucas定理2:
把n写成p进制a[n]a[n-1]……a[0];
把m写成p进制b[n]b[n-1]……b[0];(不够位数的话,显然前面是 0)
则:C(a[n],b[n])*C(a[n-1],b[n-1])*……*C(a[0],b[0])
=C(n,m) (mod p);
ps:Lucas最大的数据处理能力是p在10^5左右。
#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
const int N=1e5+;
ll n,m,p,a[N]={};
ll fpow(ll a,ll b){
ll res=;
for(;b;b>>=,a=a*a%p) if(b&) res=res*a%p;
return res;
}
ll C(ll n,ll m){
if(m>n) return ;
return a[n]*fpow(a[m],p-)%p*fpow(a[n-m],p-)%p;
}
ll lucas(ll n,ll m){
if(!m) return ;
return C(n%p,m%p)*lucas(n/p,m/p)%p;
}
int main(){
int T;cin>>T;
while(T--){
cin>>n>>m>>p;
for(int i=;i<=p;i++) a[i]=a[i-]*i%p;
cout<<lucas(n+m,n)<<'\n';
}
return ;
}
最新文章
- ECshop 数据库表结构
- 在ROS中使用Python3
- CentOS6.3编译安装Memcached集群分布式缓存代理Magent-0.6出错汇总
- CentOS6 root 用户 vi/vim 无法开启高亮
- sysbench 安装 原创
- Create RCU
- IE6解决固定定位代码
- POJ 2395 Out of Hay(最小生成树中的最大长度)
- C# 反射_基础
- sc delete 服务名
- 实现Runnable接口和扩展Thread使用场景
- C#学习心得,记录学习
- 转:JDBC驱动配置相关
- Linux基础系统优化及常用命令
- python编码,赋值和is的区别
- Win7 vs2017 WDK 1803 1809 驱动开发 出错 KMDF
- MAC OS X显示.开头的文件_苹果操作系统显示隐藏文件命令
- ext中对json数据的处理解析
- express session
- 如何1秒批量提取电脑文件夹中的所有文件、文件夹名字到txt/excel
热门文章
- 文档对象模型-DOM(二)
- 倍福TwinCAT(贝福Beckhoff)常见问题(FAQ)-TwinCAT自带的找原点功能块MC_Home怎么用
- ERROR: ld.so: object &#39;/usr/lib64/libtcmalloc.so.4&#39; from LD_PRELOAD cannot be preloaded: ignored
- C++ 和 java 使用 AES CBC 128 加解密
- mac系统中搭建apache+mysql+php的开发环境,安装mysql后,登录报错:mac ERROR 1045 (28000): Access denied for user &#39;root&#39;@&#39;localhost&#39; (using password: NO)
- html table表格导出excel的方法 html5 table导出Excel HTML用JS导出Excel的五种方法 html中table导出Excel 前端开发 将table内容导出到excel HTML table导出到Excel中的解决办法 js实现table导出Excel,保留table样式
- 用Emit技术替代反射
- 腾讯云 net.core
- CCS调试教程
- 通过虚拟驱动vivi分析摄像头驱动