【数论-Lucas定理】_MatrixYg的博客-程序员资料_lucas定理

技术标签: Lucas定理  数论  数学  

1.写在前面:我始终觉得,对于一个问题要知其然,更要知其所以然。Lucas定理在刚刚接触数论的时候就知道了,因为这是一个很常用的定理,常常和中国剩余定理放在一起考。最近在组合数学上出现了很多问题,但是都是找个结论就过去了。浑浑噩噩并不懂其中原理,感觉自己的数学直觉一直在下降,以前我甚至能够从数据中看出来数学表达式,后来学了很多的工具,就变懒了,甚至连一个稍微复杂一点的积分都懒得动手,直接自适应Simpson积过去。今天又拿起了笔,准备把Lucas定理自己证明一遍。证完之后,我似乎又看到之前的那个影子:不畏惧任何数学表达式,即使推导了十几页也毫不畏惧。废话到此结束,正题开始。

2.Lucass定理:

      

Lucas定理是同余理论中的一个很重要的定理,用于组合数取模。常常使用在问题的结果需要对某个数据取模,n,m很大,达到1e15以上,但是p在1e9以内。一般来说最好的效果实在1e5以内。看到这个式子,一个十分典型的递归,并且注意到p是素数。所以我们就会有很多疑问:这个定理怎么来的?p为什么一定要是素数?p不是素数可以吗?我们来解决这些问题。

3.在解决这个问题之前,我想说一个问题:记得是ZOJ的某次月赛吧,问题就是求:\sum_{i=0}^{n}[\binom{i}{n}==1].  其实说白了,就是统计杨辉三角形每一行中有多少个奇数。这个问题当时我打了个表,看出了规律。结论和i和n的二进制有关,但是为什么呢?

4.首先证明Lucas定理。

                  Lucas定理在数论中表述是这样的:

                     

解释一下:其实就是把a,b在p进制下表示出来,然后发现C(a,b)是和后边的式子同余的。这个式子写成递归就是上边的递归形式下的Lucas定理。递归形式下的更加易于编程,但是由于递归的存在,p不能过大。问题来了,这个结论怎么来的?继续证明。

----多项式同余-----

首先介绍一个辅助工具:多项式下的同余,其实也很容易:

f(x)=\sum_{i=0}^{i=n}ai*x^{i}          g(x)=\sum_{i=0}^{i=n}bi*x^{i}.   其中对于任意的 i \in [1,n]都有:ai和bi对同余,那么就说这两个多项式是同余的。

知道了这些,我们还需要明白这样一个结论:C \left (i,n)%n=0,对于所有的i \in [1,n-1]成立的条件是:n是质数。这个很容易证明,就不再证了。其实这里也说明了,为什么Lucas定理要求p一定是质数,而且,从这里我们也可以找出来p不是质数该如何处理。这个我们后边再讲。这样我们来看一个性质:

     \(1+x)^{p}\equiv 1+x^{p}(mod p)。这个证明可以用上边的结论证;

  (1+x)^{p}=1+C\binom{1}{n}x+C\binom{2}{n}x^{2}.....C\binom{k}{n}^{k}...+x^{p}.  我们知道中间的所有项mod p是0,所以只有第一项和最后一项。那么上式得证。

那么我们对于一般的式子:

  (x+1)^{a}\%p我们把a拆分成p进制:

                 

对于这个等式,在等式的左边,我们考虑x的b次方的系数:C(a,b)那么对于右边,其实就是在每个乘积式子中拿出一些凑出b。前边公式我们知道:b=\sum_{i=0}^{k}bi*p^{i}.也就是b在p进制下的拆分,所以对于每一个乘积式子,拿出bi。由乘法原理:C(ai,bi)的乘积即使左边x的b次方的系数。根据多项式相等的原则,我们推出:

                         

到了这里,Lucas定理得证。我们回答了第一个问题,Lucas定理是怎么来的。其实也回答了第二个问题,为什么p要是素数?因为只有p是素数才满足:对于所有的j<=p-1是成立的。那么p不是素数行吗?这个问题我们最后回答,先回答第四个问题:二项式系数:C(n,i)里面对于每一个n到底有多少个奇数?

5.二项式系数奇偶以及更加一般的C(a,b)%p=0的问题。在二项式系数中,判断是不是奇偶,其实是就是在判断:C(n,i)%2==0?.那么根据Lucas定理,这里的素数就是2.我们考虑这个式子:把n,i的二进制数位分别写出来,如果存在ai<bi,这个组合数就是0.显然是个偶数。所以我们猜想充分必要条件就是对于每一个数位,ai必须要大于bi.现在我们正面考虑:对于每一个ai>=bi,相等的时候是显然成立的。大于的时候,这个地方就是C(1,0)=1,乘起来必然是一个奇数。所以猜想得证:C(n,i)%2=1的充分必要条件是:对于i和n的二进制数位,n的每一位必须大于等于i的每一位。然后考虑每一层二项式奇数有多少?假设我用f(x)表示x的二进制数位中1的个数,对于所有的i属于[0,n],C(n,i)%2是奇数的个数就是:pow(2,f(n-1))。为什么?上边我已经证明了80%,接下来可以自己证明。那么这个结论是不是可以推广呢?答案是可以的,因为我们上来其实就说明了一个很重要的观点:a,b需要在p进制下观察,才能更好的认识这个问题。在我们证明二进制下的结论的时候,并没有很特殊的假设,只是建立在2是个质数这个结论上,所以对于所有的质数,都是成立的。那么我们可以得出下边的推论:

对于C(a,b)%p=0,p是质数。这个式子成立的条件是,对于a,b在p进制下的数位:ai,bi.只要存在一对数位使得ai<bi即可。

6.p不是质数的处理:p不是质数,就显得很棘手了。但是我们没有办法修改Lucas定理,所以只能把P变成质数,通过质因数分解

                                

那么列出同余方程:

                                  

得到了这个,我们就可以用中国剩余定理来合并答案。问题转化为如何求:这个式子的值。

我们把组合数展开:

                                  

尝试着把n!中所有pi的倍数分离,然后神奇的性质就出现了。发现n!%pi是有循环节的。这样,我们一边递归n!,一边快速幂即可求出答案。

最后放几个链接:

HDU3037:这是个裸题,直接就是结论了,C(n+m,m)%p.采用Lucas定理即可。

二项式系数奇偶问题。

洛谷Lucas定理模板

最后,给出HDU3037我AC的代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll  n, m, p;
ll Ext_gcd(ll a, ll b, ll &x, ll &y) 
{
	if (b == 0) { x = 1, y = 0; return a; }
	ll ret = Ext_gcd(b, a%b, y, x);
	y -= a / b * x;
	return ret;
}
ll Inv(ll a, int m) 
{   
	ll d, x, y, t = (ll)m;
	d = Ext_gcd(a, t, x, y);
	if (d == 1) return (x%t + t) % t;
	return -1;
}

ll Cm(ll n, ll m, ll p)  
{
	ll a = 1, b = 1;
	if (m > n) return 0;
	while (m)
	{
		a = (a*n) % p;
		b = (b*m) % p;
		m--;
		n--;
	}
	return (ll)a*Inv(b, p) % p;  
}

int Lucas(ll n, ll m, ll p)  
{
	if (m == 0) return 1;
	return (ll)Cm(n%p, m%p, p)*(ll)Lucas(n / p, m / p, p) % p;
}

int main()
{
	int  T;
	cin >> T;
	while (T--)
	{
		scanf("%lld%lld%lld", &n, &m, &p);
		printf("%d\n", Lucas(n + m, m, p));
	}
	return 0;
}

参考书籍:冯志刚《初等数论》

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_41863129/article/details/88900225

智能推荐

图解数据分析(8) | Numpy - 统计与数据科学计算工具库介绍(数据科学家入门·完结)_ShowMeAI的博客-程序员资料

n维数组是NumPy的核心概念,大部分数据的操作都是基于n维数组完成的。本系列内容覆盖到1维数组操作、2维数组操作、3维数组操作方法,本篇为系列导入文章,讲解数组的特点、与列表的对比等。......

vscode 中 matlab 编码格式显示问题_半美人的博客-程序员资料_vscode可以打开mat文件吗

vscode 中文乱码的解决方法这个问题的起源是我想用 utf8 格式去编码 matlab 代码文件,因为 utf-8 格式是通用的,但是matlab 中其实是用 GBK 具体到文件中是 gb2312,具体可以见我的这篇文章但是,这样操作,我发现一个问题。vscode 中的确是能用 utf8 对 m 文件进行编码,但在 matlab 中,中文并不能正确显示和输出,这是非常难受的。于是我想改回来...

MySQL 查找字符串位置函数_咸鱼的倔强的博客-程序员资料_mysql查找字符串位置

MySQL 查找字符串位置函数注意:本文MySQL版本为5.71、INSTR(str,substr)返回字符串str中第一次出现子字符串substr的位置,没有则返回0。官网:https://dev.mysql.com/doc/refman/5.7/en/string-functions.html#function_instrselect instr('zcxvsd1sa','b'); -- 0select instr('zcxvsd1sa','s'); -- 5select instr(

创建 VSTO 工作簿的 ClickOnce 安装包_vsto clickonce_苹果 apple的博客-程序员资料

准备工作事先创建一个Excel文件命名为“演示文档.xlsm”的,以实现通过运行名称为“演示”的宏,将A1单元格的内容复制到A2单元格中。1.在“sheet1”的A1单元格输入“1.0.0.0”,作为excel文件的版本号。2.通过开发工具中的Visual Basic,为工作簿添加模块,输入以下代码,建立宏Sub 演示() Range("A2") = Range("A1")End Sub3.文档另存为“演示文档.xlsm”。一、创建Excel VSTO工作簿的新项目...

unity3d collider自动调整大小_Unity 3D | 美术向系列教程2_地形系统介绍_weixin_39544101的博客-程序员资料

Hello . 大家好今天给大家带来U3D美术向系统教程我是麦田1前言刚发第二篇2019就过去了,提前祝大家元旦不加班吧。Unity太过于基础的就不去讲解了,网上视频教程一大把,比如界面之类的。可以去B站看看。今天水第一篇基础,地形系统。地形系统大家了解了解就Ok,当个玩具玩一玩,比较正规项目不会去用他,太费了。不排除一种情况,即地编制作大地形时候使用,再将地形转为Mesh减面。下一期将...

VSTO开发指南(VB2013版) 第一章 Office对象模型_Unknowncheats的博客-程序员资料_vsto开发

完美地将visual basic和office 办公软件结合起来。来自微软公司VSTO小组的权威专家所编著。全书共712页,内容极其全面而深入,猛一看,厚地犹如庞然大物。看完离大神就不远了哦&lt;^ . ^&gt;!!!!!《VSTO开发指南》是2008年2月电子工业出版社出版的图书,作者是(美国)Eric Carter Eric Lippert实例1:从Excel程序到...

随便推点

BOM操作常用方法_取经中的稳健少女的博客-程序员资料_bom技巧

window对象浏览器弹出框:open("http://163.com","我的网页","width=200,height=200") 视窗宽高:nnerWidth,innerHeight 和document.documentElement.clientWidth clienHeight一样浏览器窗口宽高:outerWidth,outerHeight 获取当前窗口相对屏幕的坐标:sc...

VSTO开发Powerpoint插件_agrinJPG的博客-程序员资料_ppt插件开发

不怎么熟悉VSTO的Powerpoint开发,只是突然需要用一下,但是网上相关太少了,所以这里简单记录一下。VSTO(Visual Studio Tools for Office )是VBA的替代,是一套用于创建自定义Office应用程序的Visual Studio工具包。VSTO使你可以用Visual Basic 或者Visual C#扩展Office应用程序(例如Word、Excel、InfoPath和Outlook)。你可以使用强大的Visual Studio开发环境来创建你的定制程序,而不是使

ROS2学习笔记(五)-- ROS2命令行操作常用指令总结(一)_溪风沐雪的博客-程序员资料_ros2 pkg create

简介:在前面的章节中,我们先简单学习了ROS2的话题发布和订阅,两种操作都是通过python代码实现的,而在实际应用过程中,我们会经常用到命令行操作来辅助调试,更进一步的可以使用GUI工具辅助调试,比如前边用到的rqt中的Image View工具,这一节在现有功能基础上介绍一部分常用的命令行操作指令。

Tensorflow中的subclass_weixin_44504134的博客-程序员资料_subclass='training

Loss以交叉熵为例:tf的loss api一般通过如 tf.metrics.SparseCategoricalCrossentropy(from_logits=True) 创建instance函数,或者不需要pass in参数的情况下:tf.metrics.sparse_categorical_crossentropy, 然后通过metrics(y_true, y_pred)来call这个函数Subclass损失函数需要重写 __init__()和 call() 两个函数__init__

创建 VSTO 外接程序的windows安装包_vsto环境安装包有什么用_苹果 apple的博客-程序员资料

一、创建Excel VSTO 外接程序的新项目(一)新建解决方案和Excel VSTO 外接程序项目创建一个Excel VSTO外接程序的新项目,选择“Excel VSTO外接程序(Visual Basic)”模板,命名为“外接程序安装”。VS将显示解决方案名称为“外接程序安装”,包含“外接程序安装”项目。(二)设计Excel VSTO外接程序主要是设计菜单项和代码。1.在“外接程序安装”项目上,点击右键,选择“添加”——“类”,在“添加新项-外接程序安装”界面,选择“office/sh_1671465600

PL/SQL Developer恢复默认窗口布局(2019年V13.0.0最新版PL/SQL Developer)_快乐李同学(李俊德-大连理工大学)的博客-程序员资料_plsql重置窗口布局

1.问题背景:我们刚接触PL/SQL时,可能不小心关闭了我们需要的窗口,又不知道在哪里再次恢复默认窗口布局,按照以下教程就可正常恢复PL/SQL Developer恢复默认窗口布局。2.解决方案:(1)在Configure-Preferences-User Interface-Appearance里面,有两个Reset选项。(2)Reset Toolbars和Reset Doc...

推荐文章

热门文章

相关标签