3119: 魔法
内存限制:256 MB
时间限制:1.000 S
评测方式:文本比较
命题人:外部导入
提交:0
解决:
题目描述
小奇和魔法猪是好朋友。
一天,小奇和魔法猪一起去找蛤布斯学习魔法“火球术”。“火球术”共有 n 个不同的咒语,每个咒语都是一个由小写字母组成的字符串。
现在有一张空的卷轴,小奇和魔法猪轮流在卷轴的末尾添加一个小写字母(小奇先手),一旦卷轴上的字符串包含某个咒语作为它的子串,这张卷轴就制作完成了。不幸的是,小奇和魔法猪并不是很会绘制卷轴,因此它们添加的小写字母都是随机的。
现在小奇想知道,由它完成卷轴的期望步数是多少。
输入
第一行一个正整数 n,接下来 n 行每行一个由小写字母组成的字符串。
输出
一行一个实数表示答案。当你的输出与标准输出的绝对或相对误差不超过 10^-3 时视为正确。
- 绝对误差=abs(你的答案-正确答案)
- 相对误差=abs(你的答案-正确答案) /正确答案
样例输入 复制
1
abcd
样例输出 复制
438724
提示
对于 20%的数据,所有字母均相同。
对于另外 20%的数据,单个字符串长度为 1。
对于另外 20%的数据, n=1 且所有字母均不同。
对于另外 20%的数据, n=1。
对于 100%的数据, n<=20,单个字符串长度<=10。