洛谷P1976 鸡蛋饼（Catalan数）

2024-08-30 07:04:22

P1976 鸡蛋饼

题目背景

Czyzoiers 都想知道小 x 为什么对鸡蛋饼情有独钟。经过一番逼问，小 x 道出了实情：因为他喜欢圆。

题目描述

最近小 x 又发现了一个关于圆的有趣的问题：在圆上有2N 个不同的点，小 x 想用 N 条线段把这些点连接起来（每个点只能连一条线段），使所有的线段都不想交，他想知道这样的连接方案有多少种？

输入输出格式

输入格式：

有且仅有一个正整数 N

输出格式：

要求的方案数（结果 mod 100000007）。

输入输出样例

输入样例#1：

输出样例#1：

#include<cstdio>

using namespace std;

int h[];

int main(){

    int n,i,j;

    h[]=;

    scanf("%d",&n);

    for(i=;i<=n;++i)

        for(j=;j<i;++j)

            h[i]=(h[i]+1LL*h[j]*h[i--j])%;

    printf("%d\n",h[n]);

    return ;

}

最新文章

热门文章