卡特兰数

先贴代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF=1000000007;

ll x[1020000];

ll qpow(ll num,ll pow)
{
ll ret=1;
if(pow==0) return ret;
while(pow)
{
if(pow&1) ret=(ret*num)%INF;
num=(num*num)%INF;
pow=pow>>1;
}
return ret;
}
int main()
{
ll n;
x[1]=1;
for(ll i=2;i<1019000;++i)
{
x[i]=((((i*4-2)*x[i-1])%INF)*(qpow(i+1,INF-2)%INF))%INF;
}
while(scanf("%d",&n)!=EOF)
printf("%d\n",x[n]);
return 0;
}

卡特兰数

令h(0)=1,h(1)=1,catalan数满足递推式:

h(n)= h(0)*h(n-1)+h(1)h(n-2) + … + h(n-1)h(0) (n>=2)

例如:h(2)=h(0)h(1)+h(1)h(0)=11+11=2

h(3)=h(0)h(2)+h(1)h(1)+h(2)h(0)=12+11+21=5

另类递推式 :

h(n)=h(n-1)*(4*n-2)/(n+1);

递推关系的解为:

h(n)=C(2n,n)/(n+1) (n=0,1,2,…)

递推关系的另类解为:

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

递推关系式:

在结果很大的时候我们对结果进行mod 1e9+7 运算

这个时候会产生一个问题,那就是模运算在除法下的变化

逆元

如果

则称a关于模p的乘法逆元为b

此时有

求解逆元

费马小定理:

可得

变形

对比逆元定义

可得

接下来使用快速幂算法就可以得到结果了