本文主要是介绍快速求第n个卡特兰数模板，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
卡特兰数的应用：https://blog.csdn.net/SunPeishuai/article/details/81407126
快速求第n位卡特兰数 模板：
递推法：
/*通过递推 求卡特兰数的方法*/
#include<cstdio>
#include<iostream>
using namespace std;
int main()
{int n=0;scanf("%d", &n);long long total = 1;
/* 公式 Cn=C(2n,n)/(n+1) */for (int i = 0; i < n; i++){total = total * (2 * n - i) / (i + 1);}printf("%lld",( total / (n + 1)));system("pause");return 0;}
#include<stdio.h>
//*******************************
//打表卡特兰数
//第 n个 卡特兰数存在a[n]中，a[n][0]表示长度；
//注意数是倒着存的，个位是 a[n][1] 输出时注意倒过来。
//*********************************
int a[105][100];
void ktl()
{int i,j,yu,len;a[2][0]=1;a[2][1]=2;a[1][0]=1;a[1][1]=1;len=1;for(i=3;i<101;i++){yu=0;for(j=1;j<=len;j++){int t=(a[i-1][j])*(4*i-2)+yu;yu=t/10;a[i][j]=t%10;}while(yu){a[i][++len]=yu%10;yu/=10;}for(j=len;j>=1;j--){int t=a[i][j]+yu*10;a[i][j]=t/(i+1);yu = t%(i+1);}while(!a[i][len]){len--;}a[i][0]=len;}}
int main()
{ktl();int T, n;scanf("%d", &T);while(T--){scanf("%d",&n);for(int i=a[n][0];i>0;i--){printf("%d",a[n][i]);}puts("");}return 0;
}
1
MOD1e9+7
模板：
#include <iostream>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#define ULL unsigned long long
using namespace std;long long n;
const long long M=1000000007;
long long inv[1000010];
long long last,now=1;void init()
{inv[1]=1;for(int i=2;i<=n+1;i++)inv[i]=(M-M/i)*inv[M%i]%M;
}int main()
{scanf("%lld",&n);init();for(int i=2;i<=n;i++){last=now;now=last*(4*i-2)%M*inv[i+1]%M;}printf("%lld\n",last);return 0;
}
这篇关于快速求第n个卡特兰数模板的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
