Lucas定理详解
这篇博客是从另一位园友那里存的,但是当时忘了写原文的地址,如果有找到原文地址的请评论联系!
Lucas定理解决的问题是组合数取模。数学上来说,就是求 \(\binom n m\mod p\)。(p为素数)
这里\(n,m\)可能很大,比如达到\(10^{15}\),而\(p\)在\(10^9\)以内。显然运用常规的阶乘方法无法直接求解,所以引入Lucas定理。
Lucas定理
把\(n\)和\(m\)写成\(p\)进制数的样子(如果长度不一样把短的补成长的那个的长度):
\(n=(a0a1…ak)p\)
\(m=(b0b1…bk)p\)
那么:
\(\binom n m \equiv \prod _{i=0}^k \binom {a_i} {b_i} \mod p\)
证明
如果把Lucas定理从递归的角度理解,它其实是这样的:
设\(n=ap+b,m=cp+d,(b,d<p,a=\lfloor\frac{n}{p}\rfloor,c=\lfloor \frac{m}{p}\rfloor) \\ \binom n m \equiv \binom a c * \binom b d\)
这个定理的一个很巧妙的证法是通过二项式定理来说明上面的式子是成立的。
首先,对于任意质数\(p\),有:
\((1+x)^p\equiv 1+x^p\mod p\)
其证明可以由费马小定理\((x^p \equiv x \mod p) |p为素数)\)直接得出:
\((1+x)^p\equiv 1+x\)
\(x^p\equiv x\)
所以\((1+x)^p\equiv 1+x \equiv 1+x^p\)
(当然同样也有\((a+b)^p\equiv a^p+b^p \mod p\),具体为什么你可以拆开前面的式子,将其除 \(a^p\) 和 \(b^p\) 项外的所有项的系数好好研究一下(其实就是杨辉三角的第p层),可以发现把对称项系数分别合并后都能整除\(p\))
利用这个性质,我们证明Lucas定理:
\(\begin{aligned} (1+x)^n&=(1+x)^{\lfloor \frac{n}{p}\rfloor *p}(1+x)^b \\ &=(1+x^p)^{\lfloor \frac{n}{p}\rfloor}(1+x)^b \\ &=\sum _{i=0}^k\binom {\lfloor \frac{n}{p}\rfloor} ix^{pi}\sum _{j=0}^k\binom b jx^j \end{aligned}\)
考察等式左右两边xmxm的系数,可以发现:
\(\begin{aligned} 左边&=\binom n m \\ 右边&=\binom {\lfloor \frac{n}{p}\rfloor} i\binom b j,(pi+j=m,j<p) \\ &=\binom {\lfloor \frac{n}{p}\rfloor} {\lfloor \frac{m}{p}\rfloor} \binom b d \end{aligned}\)
所以上面的式子成立,证明完毕。
如果不算预处理什么的,算法时间复杂度为\(O(log_pn)\)。如果能够支持预处理,那么就加一个\(O(p)\),要不就用快速幂,乘上\(O(logp)\)。
最新文章
- 李洪强漫谈iOS开发[C语言]-045-循环结构
- Thrift 个人实战--Thrift 网络服务模型
- PHP session 跨子域问题
- 通过自关联替代开窗函数实现SQL优化
- 【HDOJ】4267 A Simple Problem with Integers
- 【SQL语句】 - Ctrl+3 查询表属性的存储过程 [sp_select_talberowName]
- Python学习笔记 (1) :python简介、工具、编码及基础运算
- struts2总结【转载】
- 2-07. 素因子分解(20) (ZJUPAT 数学)
- CoreGraphics--画线/圆/矩形
- DataReader和DataSet区别
- Android 异步消息处理机制终结篇 :深入理解 Looper、Handler、Message、MessageQueue四者关系
- 20180117MySQL出现Waiting for table metadata lock的原因以及解决方法
- LeetCode_p150_逆波兰表达式计算/后缀表达式计算
- Docker使用docker-compose.yml构建Asp.Net Core和Mysql镜像并与Mysql数据库通信
- vue.js笔记总结
- 【C语言】符号优先级
- JAVA SpringBoot 项目打包(JAR),在打包成 docker 镜像的基本方法
- 〖Linux〗让Kubuntu的“启动栏”与Win7“任务栏”的界面和功能一样
- 6.后台验证码-session作用域
热门文章
- jmeter并发定时器
- decompressedResponseImageOfSize:completionHandler:]_block_invoke
- lwz-过去一年的总结(15-16)
- js 判断是什么浏览器、是否为谷歌浏览器
- QR 分解
- C# 文件操作的工具类
- Leetcode 7 反转整数Reverse Integer
- 【线段树】uoj#228. 基础数据结构练习题
- 【树状数组 离散化】bzoj1573: [Usaco2009 Open]牛绣花cowemb
- 九:SQL之DQL数据查询语言多表操作