2X岁，是学生です

0%

卡特兰数

发表于 更新于 分类于
本文字数： 2.5k 阅读时长 ≈ 2 分钟

满足条件的01序列

求给定 $n$ 个 $0$ 和 $n$ 个 $1$，它们将按照某种顺序排成长度为 $2n$ 的序列，满足任意前缀中 $0$ 的个数都不少于1的个数的序列的数量，答案对 $10^9+7$ 取模。

思路：

alt

可以发现，在第一次穿过红线的点开始做关于红线的对称，发现非法解都会走到 $(n - 1, n + 1)$，显然有：

这是卡特兰数的一个重要变形式，即在所有可能选法中去除非法的选法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
using namespace std;

const int mod = 1e9 + 7;
typedef long long ll;

int qmi(int x, int k, int p)
{
	int res = 1;
	while (k)
	{
		if (k & 1)
			res = (ll) res * x % mod;
		x = (ll) x * x % mod;
		k >>= 1;
	}
	return res;
}

int c(int a, int b)
{
	if (a < b)
	  return 0;
	int res = 1;
	for (int i = 1, j = a; i <= b; ++i, --j)
	{
		res = (ll) res * j % mod;
		res = (ll) res * qmi(i, mod - 2, mod) % mod;
	}
	return res;
}

int main()
{
	int n;
	cin >> n;
	int res = (ll) c(2 * n, n) * qmi(n + 1, mod - 2, mod) % mod;
	cout << res << endl;
	return 0;
}

不同的二叉搜索树(LeetCode96.不同的二叉搜索树)

给定一个整数 $n$，求以 $1,…,n$ 为节点组成的二叉搜索树有多少种？

结果对 $10^9+7$ 取模后输出。

思路：

这道题没有思路，看了答案才发现这也是一道卡特兰数相关的问题。

二叉搜索树的定义：

二叉搜索树(BST,Binary Search Tree)，或是一棵空树，或是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉搜索树。

二叉树结构上的不同，可以表现为其根节点的左右子树形式上的不同（根节点的值也不一定相同），即考虑左子树有 $0, 1, …, n - 1$ 个节点时的二叉搜索树结构数。而且只要满足二叉搜索树的性质，就能构成二叉搜索树，因此 $1$ 到 $n$ 这些数是一定可以构成 BST 的，并且不用考虑谁是根节点，以及每个节点的值是多少。

我们以 $f[i]$ 表示有从 $1$ 到 $i$ 这 $i$ 个值时能够组成的二叉搜索树的数量。同时，零个值时可以构成一颗空二叉搜索树，即 $f[0] = 1$。因此所有二叉树为：

（总共 $n$ 个点，根节点有一个点，其中一颗子树拿走 $i$ 个点，另一子树拿走剩余的 $n - 1 - i$ 个点）

该公式为卡特兰数的递推公式。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;

const int N = 1010, mod = 1e9 + 7;
int f[N];

int main()
{
    int n;
    cin >> n;
    f[0] = 1;
    for(int i = 1; i <= n; ++i)
        for(int j = 0; j <= i - 1; ++j)
            f[i] = (f[i] + (long long) f[j] * f[i - j - 1]) % mod;
    cout << f[n] << endl;
    return 0;
}

一道简单卡特兰数应用

栈是计算机中经典的数据结构，简单的说，栈就是限制在一端进行插入删除操作的线性表。

栈有两种最重要的操作，即pop（从栈顶弹出一个元素）和push（将一个元素进栈）。 

栈的重要性不言自明，任何一门数据结构的课程都会介绍栈。

宁宁同学在复习栈的基本概念时，想到了一个书上没有讲过的问题，而他自己无法给出答案，所以需要你的帮忙。

宁宁考虑的是这样一个问题：一个操作数序列，从$1,2…$一直到 $n$，栈A的深度大于 $n$。 

现在可以进行两种操作：

1、将一个数，从操作数序列的头端移到栈的头端（对应数据结构栈的push操作）。
2、将一个数，从栈的头端移到输出序列的尾端（对应数据结构栈的pop操作）。

使用这两种操作，由一个操作数序列就可以得到一系列的输出序列。

你的程序将对给定的 $n$，计算并输出由操作数序列 $1,2,…,n$ 经过操作可能得到的输出序列的总数。

输入格式
输入文件只含一个整数 n。

输出格式
输出文件只有一行，即可能输出序列的总数目。

数据范围
$ 1≤n≤18$

思路：

很显然的卡特兰数题，数据范围很小，可以直接递推出结果。

用到组合数的递推式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;

const int N = 20;
int c[2 * N][N];

int main()
{
    int n;
    cin >> n;
    c[0][0] = c[1][0] = c[1][1] = 1;
    for(int i = 2; i <= 2 * n; ++i)
    {
        c[i][0] = 1;
        for(int j = 1; j <= i; ++j)
            c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
    }
    cout << c[2 * n][n] - c[2 * n][n - 1] << endl;
    return 0;
}

参考资料

二叉搜索树