P17393 [ICPC 2018 Shenyang R] Sequences Generator

The RBM Second Generation of Dual Core Microprocessor Chip, also known as RBM2gDCMC, can generate a digital sequence of length $n$. Each digit in a sequence provided by RBM2gDCMC is regarded as an integer between $1$ and $n$ in this problem. Now I will show you the passcode for the email belonging to Gini Romety, which is a sequence of length $m$ with integers between $1$ and $n$. You are asked to calculate the probabilities of the coincidence with Gini Romety's passcode for all consecutive subsequence of length $m$ in a sequence generated by RBM2gDCMC.

The input contains several test cases, and the first line contains a positive integer $T$ indicating the number of test cases which is up to $5000$. For each test case, the first line contains two integers $n$ and $m$, satisfying $1 \leq m \leq n \leq 3 \times 10^5$, which are described as above. The following $n$ lines describe the generating logic for all digits in a sequence built by RBM2gDCMC. The $i$-th line of them contains two integers $l_i$ and $r_i$, satisfying $1 \leq l_i \leq r_i \leq n$ and $r_i - l_i \leq 9$, and $(r_i - l_i + 1)$ following integers, denoted by $w_{i, l_i}, w_{i, l_i + 1}, \cdots, w_{i, r_i}$, where $0 \leq w_{i, j} \leq 10^9$ and $\sum_{j}{w_{i, j}} = 10^9$. These data indicate that for the $i$-th digit the probability of being an integer $j$ in $[1, l_i) \cup (r_i, n]$ is zero, and the probability of being an integer $j$ in $[l_i, r_i]$ is $\frac{w_{i, j}}{10^9}$. The next line contains $m$ integers, denoted by $b_1, b_2, \cdots, b_m$, describing the passcode for Gini Romety's email, where $1 \leq b_1, b_2, \cdots, b_m \leq n$. We guarantee that the sum of $n$ in all test cases is no larger than $2 \times 10^6$.

For each test case, output a line containing "Case #x:" (without quotes) at first, where $\text{x}$ is the test case number starting from $1$. After that, output $(n - m + 1)$ lines such that the $i$-th of them contains a real number indicating the probability of the coincidence for the passcode of Gini Romety's email and the subsequence of a sequence produced by RBM2gDCMC from the $i$-th digit to the $(i + m - 1)$-th one with an absolute error of at most $10^{-9}$. Precisely speaking, assume that your answer is $a$ and the jury's answer is $b$, your answer will be considered correct if $|a - b| \le 10^{-9}$, where $|x|$ means the absolute value of $x$.

In the sample case, the probability matrix $\mathbf{P} = (p_{i, j})$ is $$ \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} $$ and thus the answers in the output are * $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$ respectively.