#1496. [L1-6] 乱码试卷

注意：

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

对于两个由汉字构成的字符串 $S=s_1s_2\cdots s_n$ 以及 $T=t_1t_2\cdots t_m$，其中 $s_i$（$1\le i\le n$）和 $t_i$（$1\le i\le m$）为汉字，我们称 $S$ 是 $T$ 的前缀，当且仅当 $n\le m$，且 $\forall 1\le i\le n$，满足 $s_i=t_i$。

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

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

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

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

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

例如，设 $D=\{\texttt{huo che, che zhan}\}$，$S=\texttt{xi an huo che zhan}$，那么最终 $T=\texttt{xi, an, huo che, zhan}$。

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

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

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

$$x\cdot\sum_{i=0}^{5}\left(\frac{i\cdot a_i}{a}\right)$$

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

第 $2\sim d+1$ 行描述词典的词语，每行一个整数表示词语的汉字个数，而后给出词语的拼音序列。

第 $d+2$ 行给出 $S$ 的汉字字符串的拼音序列。

第 $d+3$ 行给出目标汉字 $C$ 的拼音。

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

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

样例输入 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

经过分词，$T=\texttt{ni, wei shen me, bu, shi fang, yi xie, shi bing, ne}$。词语总数为 $7$，有两个词语含一个汉字 $\texttt{shi}$。代入公式得期望为：

$$10 \times \frac{2}{7}=\frac{20}{7}=2.85714285\cdots$$

样例输入 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

经过分词，$T=\texttt{wo men, he, tong shi, de, jiao wang, wang wang, yi, gong zuo, he, shi ye, wei, he xin}$（$\texttt{he}$ 有两个）。词语总数为 $12$，有一个词语含一个汉字 $\texttt{wang}$，有一个词语含两个汉字 $\texttt{wang}$。代入公式得期望为：

$$31\times \frac{1 \times 1 + 1 \times 2}{12}=\frac{31}{4}=7.75$$

$1\le n \le 2 \times 10^4$

$0\le d \le 200$

$1\le x\le 10^4$