组合数取模（卢卡斯定理）

63 阅读 0 评论 42 点赞

我是靠谱客的博主神勇发带，最近开发中收集的这篇文章主要介绍组合数取模（卢卡斯定理），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

组合数取模（卢卡斯定理）模板

const int N=1e5+5;
const int mod=10007;
ll fac[N];//用于求取阶乘取模
ll n;

void init() {
    fac[0]=1;
    for(int i=1;i<=mod;i++)
        fac[i]=fac[i-1]*i%mod;
}

ll quick_pow(ll a,ll b) {
    ll ans=1,base=a;
    while(b) {
        if(b&1) ans=ans*base%mod;
        base=base*base%mod;
        b>>=1;
    }
    return ans;
}

ll C(ll n,ll m) {
    if(m>n) return 0;
    return fac[n]*quick_pow(fac[m]*fac[n-m]%mod,mod-2)%mod;//此处运用公式C(n, m) mod p = n!/(m!(n - m)!) mod p
}

ll Lucas(ll n,ll m) {
    if(m==0) return 1;
    else return C(n%mod,m%mod)*Lucas(n/mod,m/mod)%mod;
}

推倒过程

/*
 *卢卡斯定理：组合数取模运算
 *Lucas定理是用来求 C(n,m) mod p，p为素数的值。（注意：p一定是素数）
 *C(n, m) = C(n - 1，m) + C(n - 1, m - 1) （ 提示：C(n, m) mod p = n!/(m!(n - m)!) mod p ）
 *表达式：C(n,m)%p=C(n/p,m/p)*C(n%p,m%p)%p。
 *递归方程：(C(n%p, m%p)*Lucas(n/p, m/p))%p。（递归出口为m==0，return 1）
 *机器人走方格递推公式：h(n)=C(2n,n)/(n+1)
 */

题目链接51Nod - 1120

首先看我们可以用传统dp列举前10个数来找下规律

#include<iostream>
#include<cstring>

using namespace std;

int n,dp[1005][1005];


int main(){
    for(int n=1;n<=10;n++){
        memset(dp,0,sizeof(dp));
        dp[0][0]=1;
        for(int i=1;i<n;i++){
            for(int j=0;j<=i;j++)
                dp[i][j]=dp[i][j-1]+dp[i-1][j];
        }
        cout<<dp[n-1][n-1]<<endl;
    }
    return 0;
}

得到的规律数字为：

1
1
2
5
14
42
132
429
1430

4862

This is 卡特兰数，不要问我问么知道的，我也是第一次见，然后百度得到公式如下：

递推关系的解为：
h(n)=C(2n,n)/(n+1) (n=0,1,2,...)

递推关系的另类解为：

h(n)=c(2n,n)-c(2n,n-1)(n=0,1,2,...)

哈哈然后一道dp题就转化为了数论题

代码

#include <bits/stdc++.h>
#define me(x,y) memset(x,y,sizeof(x))
#define sd(x) scanf("%d",&x)
#define ss(x) scanf("%s",x)
#define sf(x) scanf("%f",&x)
#define slf(x) scanf("%lf",&x)
#define slld(x) scanf("%lld",&x)
#define pd(x) printf("%dn",x)
#define plld(x) printf("%lldn",x)
#define ps(x) printf("%sn",x)
#define max(x,y) (x>=y?x:y)
#define min(x,y) (x<y?x:y)
#define sum(x,y) (x+y)
#define INF 0x3f3f3f3f

using namespace std;
typedef long long ll;
const int N=1e5+5;
const int mod=10007;
ll fac[N];//用于求取阶乘取模
ll n;

void init() {
    fac[0]=1;
    for(int i=1;i<=mod;i++)
        fac[i]=fac[i-1]*i%mod;
}

ll quick_pow(ll a,ll b) {
    ll ans=1,base=a;
    while(b) {
        if(b&1) ans=ans*base%mod;
        base=base*base%mod;
        b>>=1;
    }
    return ans;
}

ll C(ll n,ll m) {
    if(m>n) return 0;
    return fac[n]*quick_pow(fac[m]*fac[n-m]%mod,mod-2)%mod;//此处运用公式C(n, m) mod p = n!/(m!(n - m)!) mod p
}

ll Lucas(ll n,ll m) {
    if(m==0) return 1;
    else return C(n%mod,m%mod)*Lucas(n/mod,m/mod)%mod;
}

int main() {
    init();
	slld(n);
	n-=1;
	plld(2*Lucas(2*n,n)*quick_pow(n+1,mod-2)%mod);
	return 0;
}