RandomFA

题目背景

研究员林澈正在测试一台随机字符识别器。识别器内部维护着一个状态，每读入一个字符，就会按照预先设定的概率跳转到新的状态。由于转移具有随机性，即使输入同一个字符串，最终状态也可能不同。

现在，林澈准备从所有长度不超过给定上限的字符串中等概率选取一个作为输入。他想知道：识别器处理完整个字符串后，停在指定状态的概率是多少？

题目描述

一个随机有限自动机（Randomized Finite Automaton，简称 RFA）维护一个状态变量，初始状态为 0。

输入字符只可能是 'a'、'b' 或 'c'。当自动机读入一个字符时，它会根据当前状态和该字符对应的规则，随机转移到新的状态。

设普通状态编号为 0 到 N-1。对于字符 'a'，状态 i 的转移规则由 rulesa[i] 描述；字符 'b' 和 'c' 的规则分别由 rulesb[i]、rulesc[i] 描述。

每条规则是一个由空格分隔的列表，格式为：

st:prob st:prob ...

其中：

• st 表示转移后的普通状态编号；
• prob 表示以百分数计的转移概率。

例如，规则

1:25 3:40

表示以 25% 的概率转移到状态 1，以 40% 的概率转移到状态 3。

一条规则中列出的概率之和可能小于 100。此时，剩余概率全部用于转移到特殊状态 999。例如，上述规则还有 35% 的概率转移到状态 999。

一条规则中没有出现的普通状态，其转移概率视为 0。空规则表示以 100% 的概率转移到状态 999。

状态 999 是吸收态：一旦自动机进入状态 999，无论之后读入什么字符，都会一直停在 999。

处理字符串时，自动机按照从左到右的顺序逐个读入字符。

在所有长度不超过 maxLength 的字符串中，包括长度为 0 的空串，每一个具体字符串被选中的概率都相同。求自动机处理完整个字符串后停在 finalState 的概率。

长度恰好为 k 的字符串共有 $3^k$ 个，因此参与等概率选择的字符串总数为

$$1+3+3^2+\cdots+3^{\text{maxLength}}.$$

输入格式

第一行包含一个整数 N，表示普通状态的数量，同时也是 rulesa、rulesb 和 rulesc 的元素个数。

接下来 N 行依次给出 rulesa[0] 到 rulesa[N-1]。

再接下来 N 行依次给出 rulesb[0] 到 rulesb[N-1]。

再接下来 N 行依次给出 rulesc[0] 到 rulesc[N-1]。

每个元素占一整行。若某个元素为空字符串，则对应输入行为一个空行。即使规则为空，这一行也不能省略。

接下来一行包含一个整数 finalState，表示目标状态。

最后一行包含一个整数 maxLength，表示字符串的最大长度。

输出格式

输出一个实数，表示自动机最终停在 finalState 的概率。

当输出结果与标准答案的绝对误差或相对误差不超过 $10^{-9}$ 时，答案视为正确。

样例 1

输入

1
0:100


999
1

输出

0.5

解释

需要考虑的字符串为：空串、a、b、c。

空串和 a 最终停在状态 0，b 和 c 最终停在状态 999，因此答案为 $2/4=0.5$。

样例 2

输入

2
1:100
0:100
1:100
0:100
1:100
0:100
1
3

输出

0.75

解释

所有偶数长度的字符串最终停在状态 0，所有奇数长度的字符串最终停在状态 1。

长度为 0、1、2、3 的字符串数量分别为 1、3、9、27，其中奇数长度字符串共有 $3+27=30$ 个，总字符串数为 $40$，故答案为 $30/40=0.75$。

样例 3

输入

5
1:25 2:25 3:25 4:25
0:100
0:100
0:100
0:100










3
5

输出

0.0020604395604395605

解释

rulesb 和 rulesc 均包含 5 个空字符串，因此输入中间连续出现 10 个空行。

任何包含 b 或 c 的字符串都会进入状态 999。只含 a 的字符串从状态 0 出发，读入第一个 a 后等概率位于状态 1、2、3、4，读入第二个 a 后回到状态 0。

要最终停在状态 3，字符串必须只含 a，长度为奇数，并且最后以 $1/4$ 的概率到达状态 3。满足长度条件的字符串为 a、aaa、aaaaa，总字符串数为 $364$，故答案为

$$\frac{3}{364}\times\frac14.$$

样例 4

输入

1
0:54
0:77
0:89
0
10

输出

0.054965800470734884

数据范围与约定

• $1\le N\le 50$；
• rulesa、rulesb、rulesc 的元素数量均为 N；
• 每条规则字符串的长度为 0 到 50；
• 每条非空规则由若干个以单个空格分隔的 st:prob 组成；
• $0\le st<N$，且 st 不含多余前导零；
• prob 是不含前导零的正整数；
• 同一条规则中不会出现两个相同的 st；
• 同一条规则中所有 prob 之和在 0 到 100 之间；
• finalState 为 0 到 N-1 中的一个整数，或为 999；
• $0\le\text{maxLength}\le10$。