洛谷P1976 鸡蛋饼

题目背景

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

题目描述

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

输入格式

有且仅有一个正整数 N 。 （N≤2999）

输出格式

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

输入输出样例

输入 #1复制

24

输出 #1复制

4057031

Solution

一看此题，卡特兰数？心中满是得意。正好做过差不多的呀？差太多了！

这道题，彻底， 彻 底 ，  彻  底  ，让我想qs……

呵，高估自己了吧！

Algorithm

首先画图模拟

N=0　　ans=0

没有点，这还用说吗？

N=1　　ans=1

一对点，有且只有一种方案：两点相连。

N=2　　ans=2

想象成一个正方形的四个顶点：只能选择其中两对不相邻的边，当然只有两种（两横或两竖）

N=3　　ans=5

问题开始变得有趣了……

这个时候你会怎么算？暴力画图？

那时我想的倒是对的：

只考虑从一个顶点出发

这第一条线段只能连和它距离为奇数的顶点

否则会把原图形的一部分分割后，会存在奇数个顶点

最后要么剩下一个孤独的点，要么线段就会相交。

就先连距离为1的点吧

　　那么，原图的一半有了0个点，另一半有2*3-2=4个点

　　这时，因为线段不能相交

　　所以剩下的四个点成了孤独的，它们要自己连线：它们就像一个N=2时的图嘛->ans2=2!

　　所以，连接距离为1的点后，可以分出2*1种方案。

同样的，另一个距离为1的点亦是如此

还有一个距离为3的点（正对面的）

连接了以后，方案数同为两部分的方案数的乘积：N=1 * N=1 => 1

所以N=3时所有的方案为：2+2+1=5！

推广到n对点

C(n+1)=C(n)*C(0)+C(n-1)*C(1)+……C(1)*C(n-1)+C(0)*C(n)

两重循环即可解决！

Code

1 #include
     
      //不想OI一场空，千万别用万能头 2 #include
      
       //快排sort() 3 #include
       
        //能不用cin就不用 4 #include
        
          5 #include
         
        
       
      
     

Attention

最好开long long以防在加法和相乘时溢出。