Lucas 定律

2012-09-23

Lucas 定理转载请注明出处，谢谢 http://blog.csdn.net/ACM_cxlove?viewmodecontentsby---cxloveLucas 定

Lucas 定理

转载请注明出处，谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove

Lucas 定理：A、B是非负整数，p是质数。AB写成p进制：A=a[n]a[n-1]...a[0]，B=b[n]b[n-1]...b[0]。

则组合数C(A,B)与C(a[n],b[n])*C(a[n-1],b[n-1])*...*C(a[0],b[0]) modp同余

即：Lucas(n,m,p)=c(n%p,m%p)*Lucas(n/p,m/p,p)

For non-negative integers m and n and a prime p, the following congruence relation holds:

where

and

are the base p expansions of m and n respectively.

首先我们注意到 n=(ak...a2,a1,a0)p = (ak...a2,a1)p * p + a0

= [n/p]*p+a0

且m=[m/p]+b0

只要我们更够证明 C(n,m)=C([n/p],[m/p]) * C(a0,b0) (mod p)

剩下的工作由归纳法即可完成

我们知道对任意质数p: (1+x)^p == 1+(x^p) (mod p)

注意!这里一定要是质数 ................(为什么)

对模p 而言
Lucas 定律

上式左右两边的x^m的系数对模p而言一定同余(为什么),其中左边的x^m的系数是 C(n,m) 而由于a0和b0都小于p

右边的x^m ( = x^(([m/p]*p)+b0)) 一定是由 x^([m/p]*p) 和 x^b0 相乘而得 (即发生于 i=[m/p] , j=b0 时) 因此我们就有了

C(n,m)=C([n/p],[m/p]) * C(a0,b0) (mod p)

HDU 3037

http://acm.hdu.edu.cn/showproblem.php?pid=3037

基本的组合数学，C(N+M,M)然后对P取模

#include<iostream>#include<cstdio>#include<ctime>#include<cstring>#include<cstdlib>#include<vector>#define C    240#define TIME 10#define LL long longusing namespace std;LL PowMod(LL a,LL b,LL MOD){    LL ret=1;    while(b){        if(b&1) ret=(ret*a)%MOD;        a=(a*a)%MOD;        b>>=1;    }    return ret;}LL fac[100005];LL Get_Fact(LL p){    fac[0]=1;    for(int i=1;i<=p;i++)        fac[i]=(fac[i-1]*i)%p;}LL Lucas(LL n,LL m,LL p){    LL ret=1;    while(n&&m){        LL a=n%p,b=m%p;        if(a<b) return 0;        ret=(ret*fac[a]*PowMod(fac[b]*fac[a-b]%p,p-2,p))%p;        n/=p;        m/=p;    }    return ret;}int main(){    int t;    scanf("%d",&t);    while(t--){        LL n,m,p;        scanf("%I64d%I64d%I64d",&n,&m,&p);        Get_Fact(p);        printf("%I64d\n",Lucas(n+m,m,p));    }    return 0;}

HDU 4399 Xiao Ming's Hope

http://acm.hdu.edu.cn/showproblem.php?pid=4349

Lucas定理推广

#include<iostream>#include<cstdio>#include<ctime>#include<cstring>#include<cstdlib>#include<vector>#define C    240#define TIME 10#define LL long longusing namespace std;int main(){    int n;    while(scanf("%d",&n)!=EOF){        int cnt=0;        while(n){            if(n&1)               cnt++;            n>>=1;        }        printf("%d\n",1<<cnt);    }    return 0;}

热点排行

编程

Lucas 定律