洛谷P1976 鸡蛋饼
题目背景
Czyzoiers 都想知道小 x 为什么对鸡蛋饼情有独钟。经过一番逼问，小 x 道出 了实情：因为他喜欢圆。
题目描述
最近小 x 又发现了一个关于圆的有趣的问题：在圆上有2N 个不同的点，小 x 想用 N 条线段把这些点连接起来（每个点只能连一条线段）， 使所有的线段都不想交，他想知道这样的连接方案有多少种？
输入输出格式
输入格式：
有且仅有一个正整数 N
输出格式：
要求的方案数（结果 mod 100000007）。
输入输出样例
输入样例#1：
24输出样例#1：
4057031又是一道裸的卡特兰数
加上取模即可
1 #include<cstdio>
2 const int MAXN=100001;
3 inline int read()
4 {
5 char c=getchar();int x=0,flag=1;
6 while(c<'0'||c>'9') {if(c=='-') flag=-1;c=getchar();}
7 while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();return x*flag;
8 }
9 int n;
10 long long dp[MAXN];
11 int main()
12 {
13 n=read();
14 dp[0]=1;
15 int ans=0;
16 for(int i=1;i<=n;i++)
17 for(int j=0;j<i;j++)
18 dp[i]=(dp[i]+(dp[j]*dp[i-j-1])%100000007)%100000007;
19 printf("%lld",dp[n]%100000007);
20 return 0;
21 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-10-24 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录