统计和生成所有不同的二叉树(进阶)

[编程题]统计和生成所有不同的二叉树(进阶)

热度指数：933 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给出一个整数 n，如果 n < 1，代表空树，否则代表中序遍历的结果为 {1, 2, 3... n}。请输出可能的二叉树结构有多少。

输入描述:

第一行输入一个整数 n。

输出描述:

输出一个整数对 1e9 + 7 取模的值表示答案。

示例1

输入

输出

备注:

算法知识视频讲解

小邹要加油

// 打印发现答案就是卡特兰数 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)