#P3586. 字符串生成器

    ID: 2787 传统题 2000ms 256MiB 尝试: 171 已通过: 53 难度: 8 上传者: 标签>难度分类提高+/省选-字符串AC 自动机动态规划状压 DP期望方程线性代数与代数高斯消元主元选择CF2400By佚名提供

字符串生成器

字符串生成器

题目描述

有一个字符串生成器,初始时生成的字符串为空串,它每次独立地按给定概率随机生成一个小写字母,加在当前已生成字符串的后面。

给定 nn 个长度为 ll 的字符串,每个字符串由小写字母组成。

一旦所有给定字符串都至少作为连续子串出现一次,生成器就停止,并输出此时生成的整个字符串。

求输出字符串长度的期望值。

输入格式

第一行包含一个正整数 cc,表示有 cc 组数据。

每组数据的第一行包含三个正整数 n,l,tn,l,t。其中 tt 表示生成器仅会生成前 tt 个小写字母。
每组数据的第 22 至第 n+1n+1 行,每行包含一个长度为 ll 的字符串,每个字符串由前 tt 个小写英文字母组成。
每组数据的第 n+2n+2 行包含 tt 个不超过 10410^4 的正整数,设第 ii个正整数为 xx,那么字符串生成器生成第 ii 个小写字母的概率为 x104\frac{x}{10^4}。输入保证这 tt 个正整数之和为 10410^4。

输出格式

输出 cc 行,依次对应每组数据。每行一个有限实数,表示输出字符串长度的期望值。

样例

1
2 3 3
aac
abb
3333 3333 3334
40.5060771264

数据规模与约定

本题共 1010 个测试点。

对于 30%30\% 的数据,n=1n=1,c=1c=1;
对于 60%60\% 的数据,n≤4n\le 4,c≤2c\le 2;

对于 100%100\% 的数据,n≤8n\le 8,c≤20c\le 20,l≤6l\le 6,t≤10t\le 10。

其中 n=1n=1 的数据中存在一个测试点,只有你的答案和我们的答案相差小于 11 才为正确,并且这个测试点中 l=3l=3,t=3t=3;
对于其他 99 个测试点,只有你的答案和我们的答案相差小于 0.010.01 才为正确。

数据保证正确答案不会超过 5×1065\times 10^6。