首页
题库
面试
求职
课程
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
统计和生成所有不同的二叉树(进阶)
[编程题]统计和生成所有不同的二叉树(进阶)
热度指数:933
时间限制:C/C++ 2秒,其他语言4秒
空间限制:C/C++ 256M,其他语言512M
算法知识视频讲解
给出一个整数 n,如果 n < 1,代表空树,否则代表中序遍历的结果为 {1, 2, 3... n}。请输出可能的二叉树结构有多少。
输入描述:
第一行输入一个整数 n。
输出描述:
输出一个整数对 1e9 + 7 取模的值表示答案。
示例1
输入
8
输出
1430
备注:
马上挑战
算法知识视频讲解
提交运行
算法知识视频讲解
添加笔记
求解答(12)
邀请回答
收藏(11)
分享
纠错
提交结果有问题?
1个回答
0篇题解
添加回答
2
小邹要加油
// 打印发现答案就是 卡特兰数 fdp(n) = C(2n, n)/(n+1)
// 因为要对结果求模,而组合数需要用到除法,需要用 逆元 转化成乘法来求:
// (a/b)%M = a*(b的逆元)%M
// b关于模数M的逆元=
(M - M / b) * inv[M % b] % M;
#include <iostream>
using namespace std;
const long M = 1e9 + 7;
long fdp(long n) {
if (n < 2) {
return n;
}
long* inv = new long[n+2];
inv[1] = 1;
for (int i = 2; i < n + 2; i++) { // 线性求逆元:
https://blog.csdn.net/xiaoming_p/article/details/79644386
inv[i] = (M - M / i) * inv[M % i] % M;
}
long res = 1;
long m = n * 2;
for (int i = 0; i < n; i++) { // 求卡特兰数
res = (m - i) * inv[i + 1] % M * res % M;
}
res = res * inv[n + 1] % M;
delete []inv;
return res;
}
int main()
{
long n;
cin >> n;
cout << fdp(n) << endl;
return 0;
}
发表于 2019-12-21 14:54:48
回复(0)
这道题你会答吗?花几分钟告诉大家答案吧!
提交观点
问题信息
树
上传者:
小小
难度:
1条回答
11收藏
3476浏览
热门推荐
通过挑战的用户
查看代码
牛客65832...
2022-12-26 22:01:13
牛客49534...
2022-07-13 11:21:03
szu_Edison
2022-07-07 13:00:01
fancyshun
2022-06-29 10:44:08
atnanjing
2022-06-25 09:55:57
相关试题
虚拟存储器不能解决的问题是()
操作系统
评论
(4)
关于进程的状态和状态转换,下列哪一...
操作系统
评论
(1)
下列UML图中不是UML2规范新增...
UML
评论
(1)
()不是UML体系的组成部分。
UML
评论
(1)
细胞周期中属于DNA合成期的是:
细胞生物学
评论
(1)
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题
8
1430