P5196 [USACO19JAN]Cow Poetry

    • 73通过
    • 144提交
  • 题目提供者 泥土笨笨
  • 评测方式 云端评测
  • 标签 USACO 2019
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    USACO19年一月金组第一题

    题目描述

    不为Farmer John所知的是,Bessie还热衷于资助艺术创作!最近,她开始研究许多伟大的诗人们,而现在,她想要尝试创作一些属于自己的诗歌了。 Bessie认识N(1≤N≤5000)个单词,她想要将她们写进她的诗。Bessie已经计算了她认识的每个单词的长度,以音节为单位,并且她将这些单词划分成了不同的“韵部”。每个单词仅与属于同一韵部的其他单词押韵。

    Bessie的每首诗由M行组成(1≤M≤10^5),每一行必须由K(1≤K≤5000)个音节构成。此外,Bessie的诗必须遵循某个指定的押韵模式。

    Bessie想要知道她可以写出多少首符合限制条件的不同的诗。

    输入输出格式

    输入格式:

    输入的第一行包含N、M和K。 以下N行,每行包含两个整数si(1≤si≤K)和ci(1≤ci≤N)。这表示Bessie认识一个长度(以音节为单位)为si、属于韵部ci的单词。

    最后M行描述了Bessie想要的押韵模式,每行包含一个大写字母ei。所有押韵模式等于ei的行必须以同一韵部的单词结尾。不同ei值的行并非必须以不同的韵部的单词结尾。

    输出格式:

    输出Bessie可以写出的满足这些限制的不同的诗的数量。由于这个数字可能非常大,请计算这个数对1,000,000,007取余的结果。

    输入输出样例

    输入样例#1: 复制
    3 3 10
    3 1
    4 1
    3 2
    A
    B
    A
    输出样例#1: 复制
    960

    说明

    在这个例子中,Bessie认识三个单词。前两个单词押韵,长度分别为三个音节和四个音节,最后一个单词长度为三个音节,不与其他单词押韵。她想要写一首三行的诗,每行包含十个音节,并且第一行和最后一行押韵。共有960首这样的诗。以下是一首满足要求的诗(其中1,2、3分别代表第一个、第二个、第三个单词):121 123 321。

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