网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[NEERC 2005,LA 3516]多叉树遍历
成绩 | 开启时间 | 2014年09月19日 星期五 10:07 | |
折扣 | 0.8 | 折扣时间 | 2014年09月26日 星期五 10:07 |
允许迟交 | 是 | 关闭时间 | 2014年09月26日 星期五 10:07 |
输入文件 | Pyramids.in | 输出文件 | Pyramids.out |
【题目描述】
考古学家在一个古埃及金字塔中发现了一系列隐藏的洞穴。通过翻译附近墙上的象形文字,人们掌握了这些洞穴的结构。在一个金字塔内有n个由狭窄通道相连的洞穴,其中某个洞穴通过一条通道与外界连通。对于每个洞穴,从外界有且仅有一条通过通道进入该洞穴的路径。所有的洞穴都在金字塔的地下室中,因此我们可以认为它们都在同一水平面上。通道互不交叉。每一个洞穴的墙壁都被染成了某种颜色。
科学家们决定给洞穴绘制一张详细的地图,为此他们使用了一个探测机器人。这个机器人有两个元件:用以记录对每个洞穴描述的输出磁带,和一个操作栈。
最初机器人沿通道进入与外界直接相连的洞穴。当它第一次沿某条通道行走时,它将这条通道的特征放在栈顶。当它进入某个洞穴时,它将这个洞穴的颜色记录在输出磁带上。之后它将选择尚未经过的通道中最靠左的一个,并沿着这条通道继续前进。如果没有这样的通道,那么机器人就将栈顶元素弹出,沿着该通道以(与上一次经过该通道时的)反向行走。当机器人返回外界时它的任务就结束了。显然,机器人在一次旅行中至少经过每个洞穴各一次,并且以每个方向经过每个通道恰好一次。
科学家们已经把机器人派出去执行任务了。当它返回后,科学家们就开始研究输出磁带。他们失望地发现,一个输出磁带并不对应唯一的一个洞穴系统。现在他们有了一个新问题:可以有多少种洞穴系统对应输出磁带上的序列。请帮助他们解决这个问题。
因为答案可能很大,你应该输出它模1000000000的值。请注意,洞穴的拓扑结构远比它们的绝对位置重要。因此图中的(c)和(d)被认为是两种不同的洞穴系统。
【输入格式】
输入包含多组数据。每组数据仅一行,即由大写字母组成的访问序列。序列非空,且长度不超过300.输入结束标志为文件结束符(EOF).
【输出格式】
对于每组数据,输出满足条件的多叉树的数目除以10^9的余数。
【样例输入】
ABABABA
【样例输出】
5
【来源】
多叉树遍历(Exploring Pyramids,UVa1362,LA3516)
刘汝佳,《算法竞赛入门经典训练指南》表2.2