UVa 10312 - Expression Bracketing

#数学 #思维 #Catalan number
Published on 2016-02-26

题目地址

描述

在所有具有 n(n≤26)n(n\le26) 个叶子，且所有非叶子节点都有至少 22 个儿子的树中，不是完全二叉树的有多少棵？（并非原汁原味的描述，但题目说的就是这个意思）
完全二叉树：一棵树，其所有非叶子节点都有且仅有 22 个儿子。

样例输入

3
4
5
10

样例输出

1
6
31
98187

分析

首先来一个思维转换，咋一看直接求不是二叉树的很难搞，但是我们可以求出所有合法树，再减去完全二叉树的个数即可。
一个事实是，具有 nn 个叶子的完全二叉树的个数恰好等于 CnC_n，CnC_n 为卡特兰数的第 nn 项。证明简要提一下，设具有 nn 个叶子的完全二叉树的个数有 f(n)f(n) 个。
那么有 f(0)=1,f(1)=1f(0) = 1, f(1) = 1。除掉上面的情况，由于是完全二叉树，根节点必有两个儿子，依次枚举左儿子的叶子分配数量，得到：

f(x)=∑1≤i≤n−1f(i)∗f(n−i)f(x) = \sum\limits_{1\le i\le n - 1}f(i) * f(n - i)

算出 f(1)=1,f(2)=1,f(3)=2,f(4)=5f(1) = 1, f(2) = 1, f(3) = 2, f(4) = 5，结合递归式，容易发现 f(n)f(n) 等于 C(n)C(n)。
卡特兰数是有递推公式的，故可以线性时间内预处理得到：

剩下的就是求具有 nn 个叶子，且每个非叶子节点均有至少 22 个节点的树的个数了，其实在刘汝佳训练指南的例题 2-7 也有题及，也是利用卡特兰数的思想，首先至少分成两部分，我们将第一个儿子分配至多 n−1n-1 个节点，剩下的继续递归下去。这样形成的子树数量至少是 22。
其实这个序列叫超级卡特兰数，它也有递推公式：

S(n)=3(2∗n−3)S(n−1)−(n−3)S(n−2)nS(n) = \frac{3(2*n-3)S(n - 1) - (n - 3)S(n-2)}{n}

代码

//  Created by Sengxian on 2/24/16.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
//  UVa 10312 递推 + Catalan
#include <algorithm>
#include <iostream>
#include <cctype>
#include <climits>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#define br putchar('\n');
using namespace std;

inline int ReadInt() {
    int n = 0, ch = getchar();
    while(!isdigit(ch) && ch != EOF) ch = getchar();
    if(ch == EOF) exit(0);
    while(isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

typedef long long ll;
const int maxn = 26 + 3;
ll f[maxn], s[maxn];

void process() {
    f[1] = f[2] = 1;
    for(int i = 3; i < maxn; ++i)
        f[i] = (4 * i - 6) * f[i - 1] / i;
    s[1] = s[2] = 1;
    for(int i = 3; i < maxn; ++i)
        s[i] = (3 * (2 * i - 3) * s[i - 1] - (i - 3) * s[i - 2]) / i;
}

int main() {
    process();
    int n;
    while(n = ReadInt(), n)
        printf("%lld\n", s[n] - f[n]);
    return 0;
}

附加输入

18
1
2
5
21
7
8
23
9
10
14
3
15
26
22
16
24
12

附加输出

55779368219
0
0
31
8752745540025
771
3850
259124455145823
19363
98187
70296473
1
370019079
42620109348084205
47550361333961
1959106674
1416118615851221
2587937
UVa 11426 - GCD - Extreme (II)