[NEERC 2005,LA 3516]多叉树遍历

Grade Open Time Friday, 19 September 2014, 10:07 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:07 am
Allow late Yes Close Time Friday, 26 September 2014, 10:07 am
Input file Pyramids.in Output file Pyramids.out

【题目描述】


考古学家在一个古埃及金字塔中发现了一系列隐藏的洞穴。通过翻译附近墙上的象形文字,人们掌握了这些洞穴的结构。在一个金字塔内有n个由狭窄通道相连的洞穴,其中某个洞穴通过一条通道与外界连通。对于每个洞穴,从外界有且仅有一条通过通道进入该洞穴的路径。所有的洞穴都在金字塔的地下室中,因此我们可以认为它们都在同一水平面上。通道互不交叉。每一个洞穴的墙壁都被染成了某种颜色。

科学家们决定给洞穴绘制一张详细的地图,为此他们使用了一个探测机器人。这个机器人有两个元件:用以记录对每个洞穴描述的输出磁带,和一个操作栈。

最初机器人沿通道进入与外界直接相连的洞穴。当它第一次沿某条通道行走时,它将这条通道的特征放在栈顶。当它进入某个洞穴时,它将这个洞穴的颜色记录在输出磁带上。之后它将选择尚未经过的通道中最靠左的一个,并沿着这条通道继续前进。如果没有这样的通道,那么机器人就将栈顶元素弹出,沿着该通道以(与上一次经过该通道时的)反向行走。当机器人返回外界时它的任务就结束了。显然,机器人在一次旅行中至少经过每个洞穴各一次,并且以每个方向经过每个通道恰好一次。

科学家们已经把机器人派出去执行任务了。当它返回后,科学家们就开始研究输出磁带。他们失望地发现,一个输出磁带并不对应唯一的一个洞穴系统。现在他们有了一个新问题:可以有多少种洞穴系统对应输出磁带上的序列。请帮助他们解决这个问题。

因为答案可能很大,你应该输出它模1000000000的值。请注意,洞穴的拓扑结构远比它们的绝对位置重要。因此图中的(c)和(d)被认为是两种不同的洞穴系统。



【输入格式】

输入包含多组数据。每组数据仅一行,即由大写字母组成的访问序列。序列非空,且长度不超过300.输入结束标志为文件结束符(EOF).

【输出格式】

对于每组数据,输出满足条件的多叉树的数目除以10^9的余数。

【样例输入】

ABABABA

【样例输出】

5

【来源】

多叉树遍历(Exploring Pyramids,UVa1362,LA3516)

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