卢卡斯定理详解

卢卡斯定理详解简述卢卡斯定理是用于求c(n,m)modp,p为素数的值。题目中求n和m很大的组合数时,结果一般都会溢出,所以经常会求组合数%p的某个值。当p大于m时,我们可以直接根据定义求分母在模p意义下的乘法逆元求出结果:但当p<m时,分母的乘法逆元可能不存在(m可能是p的倍数),所以就轮到卢卡

大家好,欢迎来到IT知识分享网。

简述

  卢卡斯定理是用于求c(n,m) mod p,p为素数的值。
  题目中求n和m很大的组合数时,结果一般都会溢出,所以经常会求组合数%p的某个值。当p大于m时,我们可以直接根据定义求分母在模p意义下的乘法逆元求出结果:

  卢卡斯定理详解

  但当p<m时,分母的乘法逆元可能不存在(m可能是p的倍数),所以就轮到卢卡斯定理出场了。

定理描述

  对于非负整数n,m和质数p

  卢卡斯定理详解

  其中卢卡斯定理详解卢卡斯定理详解为n和m的p进制展开。

  在做题中我们用到的是递推式:卢卡斯定理详解

  当m<n时,规定c(n,m)=0。

证明

  设x是任意小于p的正整数,那么有:

    卢卡斯定理详解

  因为x<p,所以x存在modp意义下的逆元,于是乎:

    卢卡斯定理详解

  因为等式右边是p的倍数,所以:

    卢卡斯定理详解   公式1


   根据二项式定理,在modp意义下,我们有

    卢卡斯定理详解

  当n=p时,根据公式1,除了i=0和i=p时,其余项都为0,所以

    卢卡斯定理详解卢卡斯定理详解 公式2


  现在我们设卢卡斯定理详解卢卡斯定理详解,那么卢卡斯定理详解

  根据二项式定理,我们有:卢卡斯定理详解

  我们对等式左端进行变形:

  卢卡斯定理详解

  也就是说卢卡斯定理详解

  我们来看k=n的情况,观察卢卡斯定理详解项,左边为卢卡斯定理详解,我们现在来看右边,因为j<rm<p,同时rn<rm,我们只能取j=rn,i=qn

  于是乎我们可以得到:

  卢卡斯定理详解

  两边同时乘inv(xn),我们就可以得到:

  卢卡斯定理详解

代码详解

  根据上面的递推式,我们可以写出如下代码:  

  注意这里是n下m上,递归终点为m==0

ll lucas(ll n,ll m){
    if(m==0) return 1;
    return lucas(n/p,m/p)*c(n%p,m%p)%p;
}

  那怎么算C(n,m)呢?我们就要用到乘法逆元,根据定义来算

  这里的num[i]为i的阶层,inv(i)为i在模p意义下的乘法逆元

ll c(ll n,ll m){
    if(m>n) return 0;
    return (num[n]*inv(num[m])%p)*inv(num[n-m])%p;
}

  乘法逆元我们用费马小定理来算,这里不展开叙述

ll mypow(ll x,ll n,ll m){
    ll res=1;
    while(n){
        if(n&1) res=res*x%m;
        x=x*x%m;
        n>>=1;
    }
    return res;
}
ll inv(ll x){
    return mypow(x,p-2,p);
}

模板

卢卡斯定理详解
卢卡斯定理详解

ll num[maxn];
ll mypow(ll x,ll n,ll m){
    ll res=1;
    while(n){
        if(n&1) res=res*x%m;
        x=x*x%m;
        n>>=1;
    }
    return res;
}
ll inv(ll x){
    return mypow(x,p-2,p);
}
ll c(int n,int m){
    if(m>n) return 0;
    return (num[n]*inv(num[m])%p)*inv(num[n-m])%p;
}
ll lucas(ll n,ll m){
    if(m==0) return 1;
    return lucas(n/p,m/p)*c(n%p,m%p)%p;
}

View Code

 

  

  

   

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

   

 

   

 

 

 

 

 

 

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/30258.html

(0)

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

关注微信