Skip to content

11305: 【原1305】武功之道

题目

题目描述

author: 柏均文 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1305

Description

自从wc小奥特曼化作人类参加考试,动不动他就在考试中怒压全场,(虐场虐得)几乎心灰意冷。做题他感到难逢对手,这下又得回M78学习了。途中,他决定顺道拜访一下大怪兽大师,看看有什么能学习的。大怪兽大师正在打德州扑克,没空理小奥特曼,不过它告诉小奥特曼,中国有个叫武功的神秘东西,可以去学习学习。

于是他来到了青城山,拜师ginrat学武功。ginrat深居简出,每天只授一节课。不过他给了小奥特曼n本武功秘籍,并告诉小奥特曼,学习这些武功秘籍要按拓扑序,而且拓扑关系形成一条链。众所周知,一本秘籍其实就是好多招式,比如降龙十八掌,就只有十八招。老师一节课就讲一招(招式用小写字母‘a’-‘z’表示),但他会连续不断地讲许多天,但小奥特曼可以选择某些天去青城山玩不上课。小奥特曼当然想把秘籍全部都按顺序学习一遍。但如果他决定要学习一本秘籍(其中含有m个招式),就一定要连续m天学习,且老师这些天教授的招式不论顺序还是内容都要和秘籍上的招式一模一样(这当然要小奥特曼自己判断)。此外,当然,小奥特曼不可能同时学习两本秘籍,任两本秘籍也不可能完全一样。(ginrat老师也很机智,他的课程中包含的秘籍数不会超过他教课的天数)

他已经提前知道了武功秘籍的内容及拓扑序,也知道了老师要教什么(即课程表),他想知道有多少种方式可以学完n本秘籍。刚虐完jl考试的他不想考虑这个问题,于是找到了学霸的你。

Input Format

输入第一行为n,秘籍个数。

第2-n+1行,每行一个字符串,仅包含小写字母,为每本秘籍的招式。输入顺序即为拓扑顺序。

最后一行为一个字符串,ginrat老师的课程表。

Output Format

输出一个整数,表示学习方式的个数,对10^6取模。

Sample Input

3
ab
bc
ca
abcbcca

Sample Output

1

Hint

对40%的数据,秘籍中包含的总招式数 <= 100

对100%的数据,秘籍中包含的总招式数 <= 10000, 课程表长度 <= 700000;秘籍个数 , 每个秘籍中包含的招式数 <= 1000

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!