405417: GYM101955 B 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 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$$$.

1
5 3
1 3 100000000 200000000 700000000
1 3 600000000 150000000 250000000
1 3 333333333 333333334 333333333
3 4 450000000 550000000
1 3 999999998 1 1
1 2 3

Case #1:
0.004999999995000
0.090000000180000
0.000000000000000

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.