洛谷P1976 鸡蛋饼

题目背景

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

题目描述

最近小 x 又发现了一个关于圆的有趣的问题：在圆上有

输入格式

有且仅有一个正整数 N 。（

输出格式

要求的方案数（结果

输入输出样例

输入 #1

输出 #1

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<iostream>//不想OI一场空，千万别用万能头
 2 #include<algorithm>//快排sort()
 3 #include<cstdio>//能不用cin就不用
 4 #include<cstring>
 5 #include<map>
 6 #include<cmath>
 7 #include<vector>
 8 #define IL inline
 9 using namespace std;
10 int n;
11 long long cat[3000]={1,1};
12 int main()
13 {
14     cin>>n;
15     for(int i=2;i<=n;i++)
16     {
17         for(int j=0;j<i;j++)
18             cat[i]+=cat[i-j-1]*cat[j];
19         cat[i]%=100000007;
20 //        cout<<cat[i]<<endl;
21     }
22         
23     cout<<cat[n];
24     return 0;
25 }

Attention

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