1480. [UVa 10253] 串并联网络

【题目描述】

在这个问题中，你要计算有两个端点的串并联网络的数量。串并联网络是指电路网络的拓扑或几何属性，也就是说，没有电学功能的电路网络。两个端点中的一个叫源，另一个叫汇。

串并联网络递归定义如下：

（$1$）一条边是串并联网络。

（$2$）若 $G_1$ 和 $G_2$ 都是串并联网络，把它们的源和汇分别接在一起也能得到串并联网络。

（$3$）若 $G_1$ 和 $G_2$都是串并联网络，将 $1$ 的汇和 $2$ 的源并在一起也能得到串并联网络。

注意在串并联网络中两点之间可以有多条边，而且串联在一起的各个部分可以任意调换顺序，比如下图中的三种网络被看做相同的：

类似地，并联在一起的各个部分也可以任意调换顺序。比如下图中的三种网络也被看做相同的。

输入正整数 $N$，你的任务是统计有多少个 $n$ 条边的串并联网络。例如，$n=4$ 时有 $10$ 个，如下图：

【输入格式】

输入包含多组数据。

输入文件的每一行都有一个正整数 $N(1 \leq N \leq 30)$，为给定的边数。

输入文件以一个 $0$ 结束。

【输出格式】

对于每组数据，输出一行，即包含 $N$ 条边的串并联网络数目。

【样例输入】

1
4
15
0

【样例输出】

1
10
1399068

【提示】

对于 $30\%$ 的数据，$1 \leq N \leq 10$

对于 $100\%$ 的数据，$1 \leq N \leq 30$

【来源】

UVa 10253 Series-Parallel Networks

刘汝佳，《算法竞赛入门经典训练指南》表2.2