【递推】【卡特兰数】CODEVS 3134 Circle

新GET了一种卡特兰数的应用……

在一个圆上，有2*K个不同的结点，我们以这些点为端点，连K条线段，使得每个结点都恰好用一次。在满足这些线段将圆分成最少部分的前提下，请计算有多少种连线的方法。

不会证明，当结论记住吧。

f(i)=f(i-1)*(4*n-2)/(i+1) (2<=i<=k) (f(1)=1)

 #include<cstdio>

 using namespace std;

 long long f[]; int k;

 int main()

 {

     scanf("%d",&k); f[]=;

     for(int i=;i<=k;i++) f[i]=f[i-]*(*i-)/(i+);

     printf("%lld ",f[k]); printf("%d\n",k+);

     return ;

 }

巴特西

【递推】【卡特兰数】CODEVS 3134 Circle

最新文章

热门文章