4
23
2016
0

【组合数学“三姐妹”】卡特兰数&默慈金数&那罗延数~

模意义下生成Catalan数的前10^6项:

#include<iostream>
#include<cstdio>
using namespace std;
#define LL long long
#define N 1000005
#define MOD 1000000007
long long ans[N];
void Egcd(LL a,LL b,LL &x,LL &y){   //扩展欧几里德
    if(b==0){
        x=1;
        y=0;
        return ;  
    }
    Egcd(b,a%b,x,y);  
    LL tmp=x;
    x=y;
    y=tmp-a/b*y;  
}
int main(){
    int cas=0,n;
    int i;
    ans[0] = 0, ans[1] = 1;  
    for(i=2;i<=N;++i){
        LL x,y;
        Egcd(i+1,MOD,x,y);  //求i+1的乘法逆元x
        ans[i]=ans[i-1]*(4*i-2)%MOD*(x%MOD+MOD)%MOD;  
    }
    while(scanf("%d",&n) && n!=-1){
        printf("%lld\n",ans[n]);
    }
    return 0;
}

 

Category: 数学相关 | Tags: 数论 组合数学 学习笔记 | Read Count: 277

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com