시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
60 초 | 1024 MB | 7 | 5 | 4 | 66.667% |
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번