洛谷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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 93. [NOIP2001] 数的划分

    问题描述 将整数n分成k份,且每份不能为空,任意两种方案不能相同(不考虑顺序)。 例如:n=7,k=3,下面三种分法被认为是相同的。 1,1,5; ...

    attack
  • 洛谷P1722 矩阵 II

    题目背景 usqwedf 改编系列题。 题目描述 如果你在百忙之中抽空看题,请自动跳到第六行。 众所周知,在中国古代算筹中,红为正,黑为负…… 给定一个1*(2...

    attack
  • 2559. [NOIP2016]组合数问题

    【题目描述】 【输入格式】    从文件中读入数据。    第一行有两个整数t, k,其中t代表该测试点总共有多少组测试数据,k的意义见【问题描述】。 ...

    attack
  • HDUOJ---2546 饭卡

    饭卡 Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/O...

    Gxjun
  • 简单谈谈我的Android屏幕适配之路

    如果你还在受老板的“这个左移一个像素,再右移两个像素看看,不对不对移回来。这个大了。你没看见吗?这个变形了!”这样的气,那么学完这篇文章,你就可以回他“我已经适...

    砸漏
  • A除以B问题

    描述:本题要求计算A/B,其中A是不超过1000位的正整数,B是1位正整数。你需要输出商数Q和余数R,使得A = B * Q + R成立。

    用户2038589
  • Coins (多重背包二进制优化)

    Whuacmers use coins.They have coins of value A1,A2,A3…An Silverland dollar. One ...

    dejavu1zz
  • 提示Android屏幕适配方案分析

    Android开发过程中我们常用的尺寸单位有px、dp,还有一种sp一般是用于字体的大小。但是由于px是像素单位,比如我们通常说的手机分辨例如1920*1080...

    用户2356368
  • 爬楼梯问题详解

    说到动态规划啊,很多人都觉得是一生之敌。繁琐,耗脑子,变化多,有许多细节,不想看,不想懂。对我们这些不是专门研究算法的人来说,确实不容易把握住动态规划的所有细节...

    写代码的阿宗
  • LeetCode-Palindromic Substrings

    Given a string, your task is to count how many palindromic substrings in this st...

    卡尔曼和玻尔兹曼谁曼

扫码关注云+社区

领取腾讯云代金券