首页 > 其他分享 >Lucas(卢卡斯定理)

Lucas(卢卡斯定理)

时间:2023-06-13 18:00:35浏览次数:42  
标签:aC cp Lucas bx 定理 卢卡斯 equiv Sigma mod

\(C^m_n \equiv C^{m/p} _ {n/p} * C^{m \ mod \ p} _ {n \ mod \ p}\)

首先,我们可以知道如下定理

image

我们令 \(n = ap + b\),\(m = cp + d\)

则由二项式定理得 \((1+x)^n \equiv \Sigma_{i = 0}^nC^i_nx^i(mod \ p)\)---------(1)

由 \(n = ap + b\) 可知
\((1+x)^n \equiv (1+x)^{ap+b}\)

\((1+x)^n \equiv ((1+x)^{p})^a * (1+x)^b\)

由引理二可得

\((1+x)^n \equiv (1+x^p)^a * (1+x)^b\)

据二项式定理得

\((1+x^p)^a \equiv \Sigma_{i = 0}^aC^i_ax^{i * p}\)

\((1+x)^b \equiv \Sigma_{j=0}^bC^j_bx^j\)

\((1+x)^n \equiv \Sigma_{i = 0}^aC^i_ax^{i * p} * \Sigma_{j=0}^bC^j_bx^j\)

由于

\((1+x)^n \equiv \Sigma_{i = 0}^nC^i_nx^i(mod \ p)\)

\(\Sigma_{i = 0}^nC^i_nx^i \equiv \Sigma_{i = 0}^aC^i_ax^{i * p} * \Sigma_{j=0}^bC^j_bx^j\)

由(1)可知在 \(i=m\) 时 \(x^m\) 的系数为 \(C^m_n\)

在(2)中 \(x^m=x^{cp+d}=x^{cp} * x ^ {d}\)

带入可得

\(C^m_nx^m \equiv C^c_ax^{cp} * C^d_bx^d\)

\(C^m_nx^m \equiv C^c_aC^d_bx^{cp} * x^d\)

显然

\(C^m_n \equiv C^c_aC^d_b(mod \ p)\)

即 \(C^m_n \equiv C^{m/p} _ {n/p} * C^{m \ mod \ p} _ {n \ mod \ p}\)

标签:aC,cp,Lucas,bx,定理,卢卡斯,equiv,Sigma,mod
From: https://www.cnblogs.com/jueqingfeng/p/17478366.html

相关文章

  • 奈奎斯特采样定理中的奈奎斯特到底是谁?
    当用手机和家人通话、视频的时候,你有没有想过你的声音、影像为什么能传送到千里之外的地方? 这个问题还要从模拟信号说起。模拟信号是指用连续变化的物理量表示的信息。我们所在的世界中充满了各种各样的模拟信号,如声音、温度、湿度、压力、转速等等。可是这些连续的信号对于只知道......
  • 隐函数存在唯一性定理
    ......
  • k 倍区间(同余定理,组合数)
    题目描述给定一个长度为 N 的数列,1,2,⋯A1​,A2​,⋯AN​,如果其中一段连续的子序列 ,+1,⋯(≤)Ai​,Ai+1​,⋯Aj​(i≤j) 之和是 K 的倍数,我们就称这个区间 [,][i,j] 是 K 倍区间。你能求出数列中总共有多少个 K 倍区间吗?输入格式第一行包含两个整数 N 和 K......
  • 信道容量与香农定理、信源编码、信道编码总结
    1信道容量定义1.1信道容量:信道中平均每个符号所能传递的最大互信息量$I(X;Y)$$C=\mathop{max}\limits_{p(x)}{I(X;Y)}$单位:bit/符号1.2单位时间t内信道容量:$C_t=\frac{C}{t}$单位:bit/s1.3最佳输入概率$p(x)$分布时,传输的信息能达到信道容量1.4信道容量反映信道特性,表示信......
  • 强化学习基础篇【1】:基础知识点、马尔科夫决策过程、蒙特卡洛策略梯度定理、REINFORCE
    强化学习基础篇【1】:基础知识点、马尔科夫决策过程、蒙特卡洛策略梯度定理、REINFORCE算法1.强化学习基础知识点智能体(agent):智能体是强化学习算法的主体,它能够根据经验做出主观判断并执行动作,是整个智能系统的核心。环境(environment):智能体以外的一切统称为环境,环境在与智能体......
  • POJ2154(Pólya定理与欧拉函数优化)
    题目:Color 题意:将正n边形的n个顶点用n种颜色染色,问有多少种方案(答案modp,且可由旋转互相得到的算一种) 先说说Pólya定理设Q是n个对象的一个置换群,用m种颜色涂染这n个对象,一个对象涂任意一种颜色,则在Q作用下不等价的方案数为:   |Q|为置换群中置换的个数,为将置换q表示成不相杂......
  • hdu 5768 - 中国剩余定理 + 容斥
    题解思路:利用中国剩余定理解决多个同余问题,这里需要再加一项mn=7,an=0,这样才能求出7的倍数的解,然后再需要用到容斥,2^15枚举就行了。1.扩展欧几里得: 我们观察到:欧几里德算法停止的状态是:a=gcd(a,b),b=0,那么,这是否能给我们求解xy提供一种思路呢?因为,这时候,只要a=gc......
  • 「学习笔记」(扩展)中国剩余定理
    有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?该问题出自《孙子算经》,具体问题的解答口诀由明朝数学家程大位在《算法统宗》中给出:三人同行七十希,五树梅花廿一支,七子团圆正半月,除百零五便得知。\(2\times70+3\times21+2\times15=233=2\times......
  • 数论-裴蜀定理-扩展欧几里得算法
    裴蜀定理对于任意的整数a、b,都存在一对整数x、y(注意x和y可以是负整数),使得\(ax+by=gcd(a,b)\)成立。或者可以这样描述:对方程\(ax+by=c,(a,b,c∈Z)\),只有满足\(gcd(a,b)|c\)(即a和b的最大公约数可以整除c),方程才有整数解。扩展欧几里得算法的证明已知\(gcd(a,b)=gcd(b,a\%b)\)......
  • 「闲话随笔」卢卡斯定理证明
    「闲话随笔」卢卡斯定理证明点击查看目录目录「闲话随笔」卢卡斯定理证明今天看见同桌在求导,于是问他会不会证明卢卡斯定理,他说不知道这玩意。然后突然发现我也不会......