F. [L1-6] 乱码试卷

注意：

• 由于 oj 限制，本题输入数据的所有汉字均用不带声调的拼音表示，一个拼音包含 个小写字母 ，ü 用 代替。词语是由若干个汉字构成的字符串。题面中相应的表述均用下划线标注。
• 不考虑同音字，相同的拼音即表示同一个字。
• 词语和句子中相邻汉字的拼音用空格隔开。

对于两个由汉字构成的字符串 以及 ，其中 （）和 （）为汉字，我们称 是 的前缀，当且仅当 ，且 ，满足 。

小 A 有一个词典 ，里面记录了 个词语，每个词语是由 个汉字构成的字符串，词典中不存在两个词语使得其中一个是另一个的前缀。

今天，小 A 准备出一份“乱码试卷”，他将用如下的方法来生成试卷的第一篇“文章”：
准备一篇正常文章，去掉所有标点符号组成长度为字数为 的汉字字符串 ，由于小 A 不想让生成的文章内容过于混乱，所以他先进行分词操作。操作步骤为：

1. 初始化 为一个空序列；

2. 若字典中有一个词语恰好是 的前缀（在题目约束下这样的词语不超过 个），则将这个词语加到 末尾，并删去 的这个前缀；否则将 的第一个汉字加到 中，并删去这个汉字；

3. 重复第 2 步，直到 为空串。

例如，设 ，，那么最终 。

接下来，小 A 从 中，随机地、均匀地、可重复地选取 个词语，和适量的标点符号组合在一起拼成“文章”。

给定一个汉字 。现在小 A 想知道这篇“文章”中汉字 个数的期望是多少。

具体地，设 中的词语总数为 （若出现相同的词语，则多次计算）， 中恰有 个汉字 的词语数目有 个（）（若出现相同的词语，则多次计算），则“文章”中汉字个数期望的表达式是：

第一行包含三个整数 ，分别表示词典的词语数、 的汉字个数和选取的词语数。

第 行描述词典的词语，每行一个整数表示词语的汉字个数，而后给出词语的拼音序列。

第 行给出 的汉字字符串的拼音序列。

第 行给出目标汉字 的拼音。

保证每行末尾没有多余的空格。

输出一个浮点数，表示汉字 个数的期望。你的答案和标准答案的绝对误差或者相对误差不超过 时视为正确。

样例输入 1

4 12 10
3 wei shen me
2 shi fang
2 yi xie
2 shi bing
ni wei shen me bu shi fang yi xie shi bing ne
shi

样例输出 1

2.8571428571428571

样例解释 1

经过分词，。词语总数为 ，有两个词语含一个汉字 。代入公式得期望为：

样例输入 2

7 19 31
2 gong zuo
2 he xin
2 jiao wang
2 shi ye
2 tong shi
2 wang wang
2 wo men
wo men he tong shi de jiao wang wang wang yi gong zuo he shi ye wei he xin
wang

样例输出 2

7.75

样例解释 2

经过分词，（ 有两个）。词语总数为 ，有一个词语含一个汉字 ，有一个词语含两个汉字 。代入公式得期望为：