OI题库

【题目描述】

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

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

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

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

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

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

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

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

【输入格式】

输入包含多组数据。

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

输入文件以一个0结束。

【输出格式】

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

【样例输入】

1
4
15
0

【样例输出】

1
10
1399068

【提示】

对于30%的数据，1<=N<=10

对于100%的数据，1<=N<=30

【来源】

UVa10253 Series-Parallel Networks

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