| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 60 초 | 1024 MB | 48 | 10 | 8 | 18.182% |
There are $N$ events, numbered 1ドル$ through $N$. The probability of occurrence of each event depends upon the occurrence of exactly one other event called the parent event, except event 1ドル,ドル which is an independent event. In other words, for each event from 2ドル$ to $N,ドル 3ドル$ values are given: $P_i$ denoting the parent event of event $i,ドル $A_i$ denoting the probability of occurrence of event $i$ if its parent event occurs, and $B_i$ denoting the probability of occurrence of event $i$ if its parent event does not occur. For event 1ドル,ドル its probability of occurrence $K$ is given. There are $Q$ queries that we want to answer. Each query consists of 2ドル$ distinct events, $u_j$ and $v_j,ドル and you need to find the probability that both events $u_j$ and $v_j$ have occurred.
The first line of the input gives the number of test cases, $T$. $T$ test cases follow.
The first line of each test case contains two integers $N$ and $Q$ denoting the number of events and number of queries, respectively. $N$ lines follow. The $i$-th line describes event $i$. The first line contains a single integer $K$ denoting the probability of occurrence of event 1ドル$ multiplied by 10ドル^6$. Each of the next $N-1$ lines consists of three integers $P_i,ドル $A_i$ and $B_i$ denoting the parent event of event $i,ドル the probability of occurrence of event ii if its parent event occurs multiplied by 10ドル^6,ドル and the probability of occurrence of event $i$ if its parent event does not occur multiplied by 10ドル^6,ドル respectively. Then, $Q$ lines follow, describing the queries. Each of these lines contains two distinct integers $u_j$ and $v_j$. For each query, find the probability that both events $u_j$ and $v_j$ occurred.
For each test case, output one line containing Case #x: R1 R2 R3 … RQ, where $x$ is the test case number (starting from 1) and $R_j$ is the sought probability computed for $j$-th query modulo 10ドル^9+7,ドル which is defined precisely as follows. Represent the answer of $j$-th query as an irreducible fraction $\frac{p}{q}$. The number $R_j$ then must satisfy the modular equation $R_j × q ≡ p(\text{mod }(10^9+7)),ドル and be between 0ドル$ and 10ドル^9+6,ドル inclusive. It can be shown that under the constraints of this problem such a number $R_j$ always exists and is uniquely determined.
For at most 5 cases:
For the remaining cases:
2 5 2 200000 1 400000 300000 2 500000 200000 1 800000 100000 4 200000 400000 1 5 3 5 4 2 300000 1 100000 100000 2 300000 400000 3 500000 600000 1 2 2 4
Case #1: 136000001 556640004 Case #2: 710000005 849000006
For Sample Case #1, for the first query, the probability that both events 1ドル$ and 5ドル$ occurred is given by (the probability that event 1ドル$ occurred) $×$ (probability that event 5ドル$ occurs given event 1ドル$ occurred). Event 1ドル$ would occur with probability 0ドル.2$. Given that event 1ドル$ occurred, the probability that event 4ドル$ occurs is 0ドル.8$. Therefore, the probability of occurrence of event 5ドル$ given that event 1ドル$ occurred is 0ドル.2×0.8+0.4×0.2=0.24$ (probability of event 5ドル$ occurring given than event 4ドル$ occurred $+$ probability of event 5ドル$ occurring given that event 4ドル$ did not occur). The probability that both events 1ドル$ and 5ドル$ occurred is 0ドル.2×0.24=0.048$. The answer 0ドル.048$ can be converted into fraction of $\frac{6}{125},ドル and one can confirm that the 136000001ドル$ satisfies the conditions mentioned in the output section as 136000001ドル × 125 ≡ 6(\text{mod }(10^9+7))$ and is uniquely determined. For the second query, the probability that both events 5ドル$ and 3ドル$ occurred is 0ドル.10352$.
For Sample Case #2, for the first query, the probability that both events 1ドル$ and 2ドル$ occurred is given by (the probability that event 1ドル$ occurred) $×$ (probability that event 2ドル$ occurs given event 1ドル$ occurred). As 1ドル$ is the parent event of event 2ドル,ドル the probability of event 2ドル$ occurring given event 1ドル$ occurred is $A_2$ which is 0ドル.1$. Hence, the probability that both events 1ドル$ and 2ドル$ occurred is 0ドル.3×0.1$. Hence, the output will be 3ドル × 10^{-2}\text{ mod }(10^9+7)=710000005$. For the second query, the probability of occurrence of both events 2ドル$ and 4ドル$ is 0ドル.057$.
Contest > Google > Kick Start > Google Kick Start 2021 > Round H D번