Catalan
卡特兰数是个很神奇的序列,因为很多序列都会与这个有关。(以下例子出自蓝书)
1.n个左括号和n个右括号组成的合法括号序列的数量为Catlan(n)。
2.1~n经过一个栈,形成合法出栈序列的数量也是Catlan(n)。(火车出栈问题)
3.n个节点构成的不同二叉树的数量为Catlan(n)。
4.在平面直角坐标系上,每一步都只能向上或向右走,从(0,0)走到(n,n)并且除两个端点外不接触直线y=x的路线数量为2Catlan(n-1)。
感觉上面的这些例子都是和搜索有关,因为这貌似都是最初使用搜索解决的题目?
代码
#include<cstdio>
#define ll long long
using namespace std;
int n,i,s=1,md=1e9+7;
int ksm(int a,int b)
{
int s=1;a%=md;
while(b)
{
if(b&1)s=(ll)s*a%md;
a=(ll)a*a%md;b>>=1;
}
return s;
}
int main()
{
scanf("%d",&n);
for(i=n<<1;i>n;--i)s=(ll)s*i%md*ksm(i-n,md-2)%md;//这里是2n!除一次n还剩下一次的除法(变成乘逆元)。
s=(ll)s*ksm(n+1,md-2)%md;
printf("%d",s);
return 0;
}