题目背景

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

题目描述

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

输入输出格式

输入格式：

 

有且仅有一个正整数 N

 

输出格式：

 

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

 

输入输出样例

输入样例#1： 

24

输出样例#1： 

4057031

 

 

又是一道裸的卡特兰数

加上取模即可

1 #include
       
         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