P3715 [BJOI2017]魔法咒语

    • 51通过
    • 170提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 AC自动机 字符串 构造 各省省选 2017 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    Chandra 是一个魔法天才。

    从一岁时接受火之教会洗礼之后,Chandra 就显示出对火元素无与伦比的亲和力,轻而易举地学会种种晦涩难解的法术。这也多亏 Chandra 有着常人难以企及的语言天赋,让她能轻松流利地说出咒语中那些极其拗口的魔法词汇。

    直到十四岁,开始学习威力强大的禁咒法术时,Chandra 才遇到了障碍。

    根据火之魔法规则,禁咒的构成单位是 N 个基本词汇。施法时只要凝聚精神力,说出一段用这些词语组成的长度恰好等于 L 的语言,就能释放威力超乎想象的火法术。过去的魔法师们总结了几种表达起来最连贯的组合方式,方便施法者以最快语速完成法术。

    但具有魔法和语言双重天才的 Chandra 不满足于这几种流传下来的禁咒,因为她可以毫无困难地说出普通人几乎不可能表达的禁咒语句。然而,在实际施法时,Chandra 发现有些自创禁咒念出后不但没有预期效果,反而会使自己的精神力迅速枯竭,十分难受。

    这个问题令 Chandra 万分不解。她大量阅读典籍,到处走访魔法学者,并且不顾精神折磨一次又一次尝试新咒语,希望找出问题的答案。

    很多年过去了,在一次远古遗迹探险中,Chandra 意外闯进了火之神艾利克斯的不知名神殿。根据岩土特征分析,神殿应该有上万年的历史,这是极其罕见的。Chandra 小心

    翼翼地四处探索,沿着魔力流动来到一间密室。她看见密室中央悬浮着一本书籍。在魔法保护下书籍状况完好。精通上古语言的 Chandra 读过此书,终于解开了多年的困惑。

    禁咒法术之所以威力强大,是因为咒语借用了火之神艾利克斯的神力。这本书里记载了艾利克斯生平忌讳的 M 个词语,比如情敌的名字、讨厌的植物等等。使用禁咒法术时,如果语言中含有任何忌讳词语,就会触怒神力而失效,施法者也一并遭受惩罚。

    例如,若 ”banana” 是唯一的忌讳词语,“an”、”ban”、”analysis” 是基本词汇,禁咒长度须是 11,则“bananalysis” 是无效法术,”analysisban”、”anbanbanban”是两个有效法术。注意:一个基本词汇在禁咒法术中可以出现零次、一次或多次;只要组成方式不同就认为是不同的禁咒法术,即使书写形式相同。

    谜题破解,Chandra 心情大好。她决定计算一共有多少种有效的禁咒法术。

    由于答案可能很大,你只需要输出答案模 1,000,000,007 的结果。

    输入输出格式

    输入格式:

    第一行,三个正整数 N, M, L。

    接下来 N 行,每行一个只含小写英文字母的字符串,表示一个基本词汇。

    接下来 M 行,每行一个只含小写英文字母的字符串,表示一个忌讳词语。

    输出格式:

    仅一行,一个整数,表示答案(模 10^9+7)。

    输入输出样例

    输入样例#1: 复制
    4 2 10
    boom
    oo
    ooh
    bang
    ob
    mo
    输出样例#1: 复制
    14
    输入样例#2: 复制
    3 1 3
    a
    ab
    aba
    aaa
    输出样例#2: 复制
    3
    输入样例#3: 复制
    3 1 14
    ban
    an
    analysis
    banana
    输出样例#3: 复制
    15

    说明

    【样例解释 1】

    有效的禁咒法术共有 14 种:boom/bang/oo,oo/oo/oo/oo/oo,oo/oo/ooh/ooh,

    oo/ooh/oo/ooh,oo/ooh/ooh/oo,ooh/oo/oo/ooh,ooh/oo/ooh/oo,

    ooh/ooh/boom,ooh/ooh/oo/oo,ooh/ooh/bang,ooh/bang/ooh,

    bang/oo/oo/oo,bang/ooh/ooh,bang/bang/oo。

    【样例解释 2】

    有效的禁咒法术有 a/ab, ab/a, aba 共三种。注意,ab/a 和 aba 算

    成两种不同的禁咒法术。

    【数据规模与约定】

    本题一共有 10 个测试点。

    下表是每个测试点的数据规模和约定:

    对于 100%的数据,1 ≤ N, M ≤ 50,1 ≤ L ≤ 10^8,基本词汇的长度之和不超过100,忌讳词语的长度之和不超过 100。保证基本词汇不重复,忌讳词语不重复。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。