#P5196. [USACO19JAN] Cow Poetry G
[USACO19JAN] Cow Poetry G
题目背景
USACO19 年一月金组第一题
题目描述
不为 Farmer John 所知的是,Bessie 还热衷于资助艺术创作!最近,她开始研究许多伟大的诗人们,而现在,她想要尝试创作一些属于自己的诗歌了。 Bessie 认识 ()个单词,她想要将她们写进她的诗。Bessie 已经计算了她认识的每个单词的长度,以音节为单位,并且她将这些单词划分成了不同的“韵部”。每个单词仅与属于同一韵部的其他单词押韵。
Bessie 的每首诗由 行组成(),每一行必须由 ()个音节构成。此外,Bessie 的诗必须遵循某个指定的押韵模式。
Bessie 想要知道她可以写出多少首符合限制条件的不同的诗。
输入格式
输入的第一行包含 、 和 。
以下 行,每行包含两个整数 ()和 ()。这表示 Bessie 认识一个长度(以音节为单位)为 、属于韵部 的单词。
最后 行描述了 Bessie 想要的押韵模式,每行包含一个大写字母 。所有押韵模式等于 的行必须以同一韵部的单词结尾。不同 值的行并非必须以不同的韵部的单词结尾。
输出格式
输出 Bessie 可以写出的满足这些限制的不同的诗的数量。由于这个数字可能非常大,请计算这个数对 取余的结果。
3 3 10
3 1
4 1
3 2
A
B
A
960
提示
在这个例子中,Bessie 认识三个单词。前两个单词押韵,长度分别为三个音节和四个音节,最后一个单词长度为三个音节,不与其他单词押韵。她想要写一首三行的诗,每行包含十个音节,并且第一行和最后一行押韵。共有 首这样的诗。以下是一首满足要求的诗(其中 分别代表第一个、第二个、第三个单词):。