卡特兰数模板

54 阅读 0 评论 36 点赞

我是靠谱客的博主热情篮球，最近开发中收集的这篇文章主要介绍卡特兰数模板，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

牛客网小白赛I 题目链接：https://www.nowcoder.com/acm/contest/85

推导：http://blog.csdn.net/qq_26525215/article/details/51453493

模板：

#include<bits/stdc++.h>
using namespace std;
#define Mod 998244353
#define LL long long
#define N 500005
LL fat[N];
LL inv[N];
LL finv[N];
LL n;
void Init(){
LL i,j;
for(i=2,inv[1]=1;i<N;i++) inv[i]=((Mod - Mod/i)*1ll*inv[Mod%i])%Mod;
for(i=1,fat[0]=1,finv[0]=1;i<N;i++){
fat[i]=(fat[i-1]*i)%Mod;
finv[i]=(finv[i-1]*inv[i])%Mod;
}
}
LL C(LL n,LL m){
LL res=1;
res=res*fat[n]%Mod;
res=(res*finv[m]%Mod*finv[n-m]%Mod);
return res;
}
LL Ctl(LL n){
return (C(2*n,n)-C(2*n,n-1)+Mod)%Mod;
}