Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

洛谷P1976 鸡蛋饼

三尺剑,六钧弓 2019-08-13 21:47:00 阅读数:16 评论数:0 点赞数:0 收藏数:0

题目链接点这里

题目背景

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

题目描述

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

输入格式

有且仅有一个正整数 N 。 (N2999)

输出格式

要求的方案数(结果 mod100000007)。

输入输出样例

输入 #1
24
输出 #1
4057031

 

题解:

这一题是一道非常简洁明了的漂亮的递推题。(本人认为)

首先我们知道,对于题目中圆上的任意一点,有且仅有一个点与之连线。

而又因为任意两条连线不能相交,所以就相当于一条直线把圆周划分成了两部分,我们设为A和B。

所以A部分的点不能与B部分的点相连。

正是因为这样,我们就可以将一个大圆周切成两个小圆周进行处理(是不是听起来很像分治?对,没错!)。

于是,问题就迎刃而解了!

我们设f[i]为圆上有i个点时的答案,随便找一点,枚举与它连线的i,得出递推方程式如下:

其中,f[2j-2]*f[i-2j]就相当于两边的方案数之积(搭配原理),而i%2==0是因为只有点的个数为偶数时,这些点才能两两匹配。

看到上面那两个递推方程式,你们可能会想:为什么f[0]=1呢?

那是因为:你被迫不连也是一种方案呀!(主动不连当然不符合要求)

现在你懂了吗?

如果还是没有,那就看代码吧!

代码:

 #include<bits/stdc++.h>
 using namespace std;
 int n;
 long long f[]={,,};//初始化,因为100000007*3000个数会爆int,所以开long long 
 int main()
 {
     cin>>n;
     for(int i=;i<=n*;i+=)
     {
         for(int j=;j<=i;j+=)
         f[i]+=f[j-]*f[i-j];//递推式 
         f[i]%=100000007;
     }
     printf("%d\n",f[n*]);//一定要知道,答案是n*2! 
     return ;
 }

题目到此结束!

版权声明
本文为[三尺剑,六钧弓]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/xinxiyuan/p/11348822.html