卡特兰数是一种经典的组合数,经常出现在各种计算中,其前几项为 :
1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786……
卡特兰数一般的计算公式:
Cn的另一个表达形式为
卡塔兰数满足以下递推关系
所有的奇卡塔兰数Cn都满足n = 2^k − 1。
所有其他的卡塔兰数都是偶数。
int main()
{
ios::sync_with_stdio(false);
long long Catalan[100],ans;//范围自行高精度或者取模
int n;
Catalan[0] = 1;
for(int i = 1;i < n;++i) Catalan[i] = Catalan[i - 1] * i;
while(cin >> n){
ans = Catalan[n << 1] / (Catalan[n] * Catalan[n + 1]);
cout << ans << endl;
}
return 0;
}
因篇幅问题不能全部显示,请点此查看更多更全内容