#P3586. 字符串生成器
字符串生成器
字符串生成器
题目描述
有一个字符串生成器,初始时生成的字符串为空串,它每次独立地按给定概率随机生成一个小写字母,加在当前已生成字符串的后面。
给定 个长度为 的字符串,每个字符串由小写字母组成。
一旦所有给定字符串都至少作为连续子串出现一次,生成器就停止,并输出此时生成的整个字符串。
求输出字符串长度的期望值。
输入格式
第一行包含一个正整数 ,表示有 组数据。
每组数据的第一行包含三个正整数 。其中 表示生成器仅会生成前 个小写字母。
每组数据的第 至第 行,每行包含一个长度为 的字符串,每个字符串由前 个小写英文字母组成。
每组数据的第 行包含 个不超过 的正整数,设第 个正整数为 ,那么字符串生成器生成第 个小写字母的概率为 。输入保证这 个正整数之和为 。
输出格式
输出 行,依次对应每组数据。每行一个有限实数,表示输出字符串长度的期望值。
样例
1
2 3 3
aac
abb
3333 3333 3334
40.5060771264
数据规模与约定
本题共 个测试点。
对于 的数据,,;
对于 的数据,,;
对于 的数据,,,,。
其中 的数据中存在一个测试点,只有你的答案和我们的答案相差小于 才为正确,并且这个测试点中 ,;
对于其他 个测试点,只有你的答案和我们的答案相差小于 才为正确。
数据保证正确答案不会超过 。