lucas定理和组合数学
2024-09-30 21:57:38
自湖南长沙培训以来的坑。。。一直未填,今天把这个问题解决掉。
参考:
1.http://www.cnblogs.com/Var123/p/5523068.html
2.http://blog.csdn.net/qzh_1430586275/article/details/51893154
3.http://blog.csdn.net/check_check_check/article/details/52101467
一、lucas定理的定义
(当且仅当p为质数)
很简短,下面看看应用和相关题目。
二、lucas定理的应用
1、[bzoj4591][Shoi2015][超能粒子炮·改]
题目描述:求 C(n,0)+C(n,1)+...+C(n,k)mod2333
推到过程:
易得,
原式=C(n/2333,0)∗C(nmod2333,0)+C(n/2333,0)∗C(nmod2333,1)+...+C(n/2333,k/2333)∗C(nmod2333,kmod2333) mod 2333
也就是将原式中的各个mod 2333项拆分成两项再总体mod 2333
同类项合并,分两种部分考虑:
设k=k1*2333+k2 (0≤k1,k2)
1)对于k1部分
先考虑k1=0的情况,可以得出这些乘积的各个首项是C(n/2333,0),将其提出得到C(n/2333,0)*∑C(n%2333,i)(其中i∈[0,2333])
考虑k1=1的情况,可得C(n/2333,1)*∑C(n%2333,i)(其中i∈[0,2333])
考虑k1=2的情况,可得C(n/2333,2)*∑C(n%2333,i)(其中i∈[0,2333])
··· ··· ··· ··· ··· ···
提公因式→→→∑C(n/2333,j)*∑C(n%2333,i)(其中i∈[0,2333],j∈[0,k1))
重复3遍
∑C(n/2333,j)*∑C(n%2333,i)(其中i∈[0,2333],j∈[0,k1))
∑C(n/2333,j)*∑C(n%2333,i)(其中i∈[0,2333],j∈[0,k1))
∑C(n/2333,j)*∑C(n%2333,i)(其中i∈[0,2333],j∈[0,k1))
吼,各位就等了,看看k2部分吧
2)对于k2部分
原式=C(n/2333,k1)*C(n%2333,0)+C(n/2333,k1)*C(n%2333,1)+······+C(n/2333,k1)*C(n%2333,k%2333)
=C(n/2333,k1)*(∑C(n%2333,i))(其中i∈[0,k%2333])
综上,ans=∑C(n/2333,j)*∑C(n%2333,i)(其中i∈[0,2333],j∈[0,k1))+C(n/2333,k1)*(∑C(n%2333,i))(其中i∈[0,k%2333])
说了这么多,那么这个定理的用法是什么?
显然是递归求解组合数的模数咯~
所以对于这道题,我们先预处理出一个S(n,k)=∑C(n,i) (i∈[0,k]) (当然最后都是mod p意义下的),ans=S(n%2333,2332)*(∑C(n/2333,j)) (j∈[0,k1)) + C(n/2333,k1)*S(n%2333,k%2333)
ans中的S()一定可以用二维的东西在规定时空内求出,而∑C(n/2333,j)就是我们超能粒子炮`改的子问题,递归求解即可,另,C(n/2333,k1)也可以用lucas定理递归来解
于是这道题就口头ac了。
最新文章
- 安卓基于WifiScanner的签到APP
- Windows 商店应用中使用 SharePoint REST API
- arpg网页游戏之地图(三)
- zstu.4191: 无向图找环(dfs树 + 邻接表)
- dubbo的简单使用
- C++线性方程求解
- STM32的Cortex-M3核与ARM7有何区别?哪个性能更强?
- CSS控制超链接
- 【跟我一起学Python吧】Python解释执行原理
- 解决IIS7中出现An error occurred on the server when processing the URL错误提示的方法
- JS中String的反转函数
- java代理的深入浅出(一)-Proxy
- Java编程规范(二)
- 请求库-selenium 模块
- github not authorized eclipse
- 【Android 应用开发】自定义View 和 ViewGroup
- MIT 6.824 lab1:mapreduce
- mysql分类和事务回滚
- Jenkins操作,实现增删改查
- ArcGIS js api开发环境配置
热门文章
- 用户能够在下次登录系统时被重新配置---或win10早期更新不成功的bug就需要删除多余的登陆用户
- J20170604-hm
- 洛谷 P4180 【模板】严格次小生成树[BJWC2010]【次小生成树】
- bzoj1880: [Sdoi2009]Elaxia的路线(spfa,拓扑排序最长路)
- ElementaryOS 0.4快速配置工具
- N - Binomial Showdown (组合数学)
- IIS网站部署步骤以及常见异常解决方案
- java list遍历三种方法
- poj1787 Charlie's Change
- CF816B Karen and Coffee