P17393 [ICPC 2018 Shenyang R] Sequences Generator

RBM 第二代双核微处理器芯片，也被称为 RBM2gDCMC，能够生成一个长度为 $n$ 的数字序列。在本题中，由 RBM2gDCMC 提供的序列中的每个数字被视为一个介于 $1$ 和 $n$ 之间的整数。 现在我将向你展示属于 Gini Romety 的电子邮件密码，它是一个长度为 $m$ 且由介于 $1$ 和 $n$ 之间的整数组成的序列。你需要计算 RBM2gDCMC 生成的序列中所有长度为 $m$ 的连续子序列与 Gini Romety 的密码相符的概率。

输入包含多组测试数据，第一行包含一个正整数 $T$，表示测试数据的组数，最多不超过 $5000$。 对于每组测试数据，第一行包含两个整数 $n$ 和 $m$，满足 $1 \leq m \leq n \leq 3 \times 10^5$，含义如上所述。 接下来的 $n$ 行描述了 RBM2gDCMC 构建的序列中每一位数字的生成逻辑。其中第 $i$ 行包含两个整数 $l_i$ 和 $r_i$，满足 $1 \leq l_i \leq r_i \leq n$ 且 $r_i - l_i \leq 9$，以及 $(r_i - l_i + 1)$ 个后续整数，记为 $w_{i, l_i}, w_{i, l_i + 1}, \cdots, w_{i, r_i}$，其中 $0 \leq w_{i, j} \leq 10^9$ 且 $\sum_{j}{w_{i, j}} = 10^9$。这些数据表明：对于第 $i$ 位数字，其取值为 $[1, l_i) \cup (r_i, n]$ 中整数 $j$ 的概率为零，而取值为 $[l_i, r_i]$ 中整数 $j$ 的概率为 $\frac{w_{i, j}}{10^9}$。 接下来的一行包含 $m$ 个整数，记为 $b_1, b_2, \cdots, b_m$，描述 Gini Romety 的电子邮件密码，其中 $1 \leq b_1, b_2, \cdots, b_m \leq n$。 我们保证所有测试数据中 $n$ 的总和不超过 $2 \times 10^6$。

对于每组测试数据，首先输出一行包含 “Case #$x$:”（不含引号），其中 $x$ 是测试数据的编号，从 $1$ 开始。 在此之后，输出 $(n - m + 1)$ 行，其中第 $i$ 行包含一个实数，表示 RBM2gDCMC 生成的序列中从第 $i$ 位到第 $(i + m - 1)$ 位的子序列与 Gini Romety 的电子邮件密码相符的概率，绝对误差至多为 $10^{-9}$。准确地说，假设你的答案为 $a$，裁判的答案为 $b$，若 $|a - b| \le 10^{-9}$，则你的答案视为正确，其中 $|x|$ 表示 $x$ 的绝对值。

在样例中，概率矩阵 $\mathbf{P} = (p_{i, j})$ 为 $$ \begin{bmatrix} 0.100000000 & 0.200000000 & 0.700000000 & 0.000000000 & 0.000000000 \\ 0.600000000 & 0.150000000 & 0.250000000 & 0.000000000 & 0.000000000 \\ 0.333333333 & 0.333333334 & 0.333333333 & 0.000000000 & 0.000000000 \\ 0.000000000 & 0.000000000 & 0.450000000 & 0.550000000 & 0.000000000 \\ 0.999999998 & 0.000000001 & 0.000000001 & 0.000000000 & 0.000000000 \end{bmatrix} $$ 因此输出中的答案分别为 * $p_{1, 1} p_{2, 2} p_{3, 3} = 0.100000000 \times 0.150000000 \times 0.333333333 = 0.004999999995000$， * $p_{2, 1} p_{3, 2} p_{4, 3} = 0.600000000 \times 0.333333334 \times 0.450000000 = 0.090000000180000$， * $p_{3, 1} p_{4, 2} p_{5, 3} = 0.333333333 \times 0.000000000 \times 0.000000001 = 0.000000000000000$。 翻译由 DeepSeek V4 Pro 完成