数论之Lucas定理求大组合数取模的应用常见题型汇总

Lucas定理是用来求 c(n,m) mod p，p为素数的值。
对于C(n, m) mod p。这里的n，m，p（p为素数）都很大的情况。就不能再用C(n, m) = C(n - 1，m) + C(n - 1, m - 1)的公式递推了。
应用：大组合数求模
表达式C(n,m)%p=C(n/p,m/p)*C(n%p,m%p)%p

因为p为素数，所以这类题都可以用费马小定理计算逆元。当然也可以用扩展欧几里得。
常见题型：
一 . n ,m较大,mod 为素数且较小
51nod1120卡特兰数+卢斯卡定理
因为mod较小，可以预处理出小于mod的阶乘。
Code:

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const LL MOD = 10007;
const int AX = 1e6+66;
LL f[AX];
void init( LL p ) {
    f[0] = 1LL;
    for( LL i = 1 ; i <= p ; i++ ) f[i] = ( f[i-1] * i ) % p;
}
LL quick( LL a , LL b , LL p ){
    LL ans = 1LL;
    while( b ){
        if( b & 1 ) ans = ( ans * a ) % p;
        a = ( a * a ) % p;
        b >>= 1 ;
    }
    return ans ;
} 
LL C( LL n , LL m , LL p ){
    if( m < 0 || n < m ) return 0 ;
    return f[n] * quick( f[m] , p - 2 , p ) % p * quick( f[n-m] , p - 2 , p ) % p ;
}
LL Lucas( LL n , LL m , LL p ){
    return m ? Lucas( n / p , m / p , p ) * C( n % p , m % p , p ) % p : 1 ;
}
int main(){
   LL n;
   init(MOD);
   scanf("%lld",&n);
   n--;
   LL ans = Lucas(2*n,n,MOD)*quick(n+1,MOD-2,MOD)%MOD;
   printf("%lldn",2*ans%MOD);
   return 0;
}

二 . n , m ，mod 较大，mod为素数
例题：mod<=1e9，n<=1e9, m<=1e4
Code：

#include <iostream>
#include <cstdio>
#define LL long long
using namespace std;

LL quick( LL a , LL b , LL p ){
    LL ans = 1LL;
    while( b ){
        if( b & 1 ) ans = ( ans * a ) % p ;
        a = ( a * a ) % p ;
        b >>= 1 ;
    }
    return ans ;
}

LL fac( LL x , LL p ){
    LL ans = 1;
    for( int i = 2 ; i <= x ; i ++ ) ans = ( ans * i ) % p;
    return ans;
}

LL C( LL n , LL m , LL p ){
    if( m < 0 || n < m ) return 0;
    if( m == 0 ) return 1 ;
    m = min( m , n - m );
    LL a = 1LL , b = 1LL;
    for( LL i = 1 ; i <= m ; i++ ){
        a =   a * (n - i + 1) % p ;
        b = ( b * i ) % p;
    }
    return a * quick( b , p - 2 , p ) % p ; 
}


LL Lucas( LL n , LL m , LL p ){
    return m ? C( n % p , m % p , p ) * Lucas( n / p , m / p , p ) % p : 1 ;
}

int main(){
    int T;
    LL n , m , p;
    scanf("%d",&T);
    while( T-- ){
        scanf("%lld%lld%lld",&n,&m,&p);
        LL res = Lucas( n , m , p );
        printf("%lldn",res);
    }
    return 0 ; 
}

三 . n , m 很大且mod为几个不同素数的乘积

例题
需要注意的是因为数非常大，所以如果使用费马小定理计算逆元，快速幂时需要使用快速乘法防止中间爆LL
Code：

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MOD =  1e9+7;
const int MAXN = 2e5+10;
#define LL long long
LL mul( LL a , LL b , LL p ){
    LL ans = 0LL;
    while( b ){
        if( b & 1 ) ans = ( ans + a ) % p ;
        a = ( a + a ) % p ;
        b >>= 1 ;
    }
    return ans ;
}

LL quick( LL a , LL b , LL p ){
    LL ans = 1LL;
    while( b ){
        if( b & 1 ) ans = mul( ans , a , p ) % p;
        a = mul( a , a , p ) % p;
        b >>= 1 ;
    }
    return ans ;
} 


LL fac( LL x , LL p ){
    LL ans = 1;
    for( LL i = 2 ; i <= x ; i ++ ) ans = ( ans * i ) % p;
    return ans;
}

LL C( LL n , LL m , LL p ){
    if( m < 0 || n < m ) return 0 ;
    return fac( n , p ) * quick( fac( m , p ) , p - 2 , p ) % p * quick( fac( n - m , p ) , p - 2 , p ) % p ;
}

LL CRT( LL *a , LL *m , int n ){
    LL M = 1LL , res = 0LL;
    for( int i = 0 ; i < n ; i++ ) M *= m[i];
    for( int i = 0 ; i < n ; i++ ){
        LL w = M / m[i];
        res = ( res + mul( w * quick( w , m[i] - 2 , m[i] ) , a[i] , M ) ) % M;
    }
    return ( res + M ) % M;
}

LL Lucas( LL n , LL m , LL p ){
    return m ? Lucas( n / p , m / p , p ) * C( n % p , m % p , p ) % p : 1 ;
}
int main(){
    LL n,m;
    LL p[15];
    LL a[15];
    int T,k;
    scanf("%d",&T);
    while(T--){
        scanf("%lld%lld%d",&n,&m,&k);
        for( int i = 0 ; i < k ; i++ ){
            scanf("%lld",&p[i]);
        }
        for( int i = 0 ; i < k ; i++ ){
            a[i] = Lucas( n , m , p[i] );
        }
        printf("%lldn",CRT(a,p,k));
    }
    return 0;
}

下面贴一个扩展欧几里得求逆元版本的：

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MOD =  1e9+7;
const int MAXN = 2e5+10;
#define LL long long
LL qmul(LL a,LL p,LL m){
    LL tmp = 0;
    while(p){
        if(1&p) tmp = (tmp+a)%m;
        a = (a+a)%m;
        p>>=1;
    }
    return tmp;
}
void exgcd(LL a,LL b,LL &x,LL &y,LL &d){
    if(!b) d=a,x = 1,y=0;
    else exgcd(b,a%b,y,x,d),y-=(a/b)*x;
}
LL inv(LL a,LL p){
    LL x,y,d;
    exgcd(a,p,x,y,d);
    return d==1?(x+p)%p:-1;
}
LL fat(LL x,LL p){
    LL ans = 1;
    for( int i = 2 ; i <= x ; i ++ ) ans = ( ans * i ) % p;
    return ans;
}
LL c(LL n,LL m,LL p){
    if (m < 0 || m > n) return 0; 
    return fat(n,p)*inv(fat(m,p),p)%p*inv(fat(n-m,p),p)%p;
}
LL crt(LL *a,LL *m,int n){
    LL M = 1,res = 0;
    for( int i = 0 ; i < n ; i++ ) M*=m[i];
    for( int i = 0 ; i < n ; i++ ){
        LL w = M/m[i];
        res = (res+qmul(w*inv(w,m[i]),a[i],M))%M;
    }
    return (res+M)%M;
}
LL Lucas(LL n,LL m,LL p){
    return m?Lucas(n/p,m/p,p)*c(n%p,m%p,p)%p:1;
}
int main(){
    LL n,m;
    LL p[15];
    LL a[15];
    int T,k;
    scanf("%d",&T);
    while(T--){
        scanf("%lld%lld%d",&n,&m,&k);
        for( int i = 0 ; i < k ; i++ ){
            scanf("%lld",&p[i]);
        }
        for( int i = 0 ; i < k ; i++ ){
            a[i] = Lucas( n , m , p[i] );
        }
        printf("%lldn",crt(a,p,k));
    }
    return 0;
}

4.n , m 很大且mod不一定为素数
解决方法就是将mod分解成 （p1^c1）(p2^c2) ***(pk^ck) (k 个素数 )
求 C(n,m)% pi^ci .
下面是求 C(n,m)% pi^ci的方法

待填坑。遇到题再补充。

最后

以上就是怕黑衬衫为你收集整理的数论之Lucas定理求大组合数取模的应用常见题型汇总的全部内容，希望文章能够帮你解决数论之Lucas定理求大组合数取模的应用常见题型汇总所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。