当前没有测试数据。

禁忌子串

题目描述

给定$alphabet$，令字符集为小写字母中前$alphabet$个字母。

再给定一个字符集$A$上的字符串集合$T$，$T$的大小为$N$，$T$中的每一个字符串都被称为禁忌串。

一个字符串的禁忌伤害将按照如下方式计算：将这个字符串划分为若干段，最大化其中是禁忌串的段的数量，则这个禁忌串的段的数量的最大值即为这个字符串的禁忌伤害。

求在字符集$A$上且长度为$len$的字符串的禁忌伤害的期望。

输入格式

第一行包含三个正整数$N$，$len$，$alphabet$。

接下来$N$行，每行包含一个串，表示第$i$个禁忌串。

输出格式

一个非负实数，表示答案，你的答案需要保证相对误差或绝对误差不超过$10^{-3}$。

数据范围与提示

• 对于$30\%$的数据，$len \leq 10$，$alphabet \leq 2$；
• 对于$70\%$的数据，$len \leq 50$；
• 存在$40\%$的数据，$N = 1$；
• 对于$100\%$的数据，$N \leq 5$，$len \leq 10^{9}$，$1 \leq alphabet \leq 26$，$\forall i$，$|T_{i}| \leq 15$，$T_{i}$不为空串且仅包含前$alphabet$个小写字母。

样例

2 4 2
aa
abb

0.75

1 1000000000 26
koishi

3.2371282812050