Substring

题意翻译

给出一些字符和各自对应的选择概率，随机选择 $L$ 次后将得到一个长度为 $L$ 的随机字符串 $S$ （每次独立随机）。给出 $K$ 个模板串，计算 $S$ 不包含任何一个串的概率（即任何一个模板串都不是 $S$ 的连续子串）。

题目描述

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=26&page=show_problem&problem=2463 [PDF](https://uva.onlinejudge.org/external/114/p11468.pdf) ![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA11468/84fafd962f73943396e3969808a951d9a6396c25.png)

输入输出格式

输入格式

![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA11468/b628f18a73ffe475b1f54b91f7966a08930ee3ce.png)

输出格式

![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA11468/0ee3e8fdfeca4c5c1938164143fc68971ffa328f.png)

输入输出样例

输入样例 #1

2
1
a
2
a 0.5
b 0.5
2
2
ab
ab
2
a 0.2
b 0.8
2

输出样例 #1

Case #1: 0.250000
Case #2: 0.840000