Dependent Events solution kickstart

Dependent Events solution kickstart

There are NN events, numbered 11 through NN. The probability of occurrence of each event depends upon the occurrence of exactly one other event called the parent event, except event 11, which is an independent event. In other words, for each event from 22 to NN33 values are given: PiPi denoting the parent event of event iiAiAi denoting the probability of occurrence of event ii if its parent event occurs, and BiBi denoting the probability of occurrence of event ii if its parent event does not occur. For event 11, its probability of occurrence KK is given. There are QQ queries that we want to answer. Each query consists of 22 distinct events, ujuj and vjvj, and you need to find the probability that both events ujuj and vjvj have occurred. Dependent Events solution kickstart

Input

The first line of the input gives the number of test cases, TTTT test cases follow.

The first line of each test case contains two integers NN and QQ denoting the number of events and number of queries, respectively. NN lines follow. The ii-th line describes event ii. The first line contains a single integer KK denoting the probability of occurrence of event 11 multiplied by 106106. Each of the next N1N−1 lines consists of three integers PiPiAiAi and BiBi denoting the parent event of event ii, the probability of occurrence of event ii if its parent event occurs multiplied by 106106, and the probability of occurrence of event ii if its parent event does not occur multiplied by 106106, respectively. Then, QQ lines follow, describing the queries. Each of these lines contains two distinct integers ujuj and vjvj. For each query, find the probability that both events ujuj and vjvj occurred.

Output Dependent Events solution kickstart

For each test case, output one line containing Case #xxR1 R2 R3  RQR1 R2 R3 … RQ, where xx is the test case number (starting from 1) and RjRj is the sought probability computed for jj-th query modulo 109+7109+7, which is defined precisely as follows. Represent the answer of jj-th query as an irreducible fraction pqpq. The number RjRj then must satisfy the modular equation Rj×qp(mod(109+7))Rj×q≡p(mod(109+7)), and be between 00 and 109+6109+6, inclusive. It can be shown that under the constraints of this problem such a number RjRj always exists and is uniquely determined.

Limits Dependent Events solution kickstart

Time limit: 60 seconds.
Memory limit: 1 GB.
1T1001≤T≤100.
1Pi<i1≤Pi<i, for each ii from 22 to NN.
1uj,vjN1≤uj,vj≤N and ujvjuj≠vj, for all jj.
0Ai1060≤Ai≤106, for each ii from 22 to NN.
0Bi1060≤Bi≤106, for each ii from 22 to NN.
0K1060≤K≤106.

Test Set 1

2N10002≤N≤1000.
1Q10001≤Q≤1000.

Test Set 2

For at most 5 cases:
2N2×1052≤N≤2×105.
1Q2×1051≤Q≤2×105.

For the remaining cases:
2N10002≤N≤1000.
1Q10001≤Q≤1000.

Sample Dependent Events solution kickstart

Sample Input
content_copy
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
Sample Output
content_copy
Case #1: 136000001 556640004
Case #2: 710000005 849000006

For Sample Case #1, for the first query, the probability that both events 11 and 55 occurred is given by (the probability that event 11 occurred) ×× (probability that event 55 occurs given event 11 occurred). Event 11 would occur with probability 0.20.2. Given that event 11 occurred, the probability that event 44 occurs is 0.80.8. Therefore, the probability of occurrence of event 55 given that event 11 occurred is 0.2×0.8+0.4×0.2=0.240.2×0.8+0.4×0.2=0.24 (probability of event 55 occurring given than event 44 occurred ++ probability of event 55 occurring given that event 44 did not occur). The probability that both events 11 and 55 occurred is 0.2×0.24=0.0480.2×0.24=0.048. The answer 0.0480.048 can be converted into fraction of 61256125, and one can confirm that the 136000001136000001 satisfies the conditions mentioned in the output section as 136000001×1256(mod(109+7))136000001×125≡6(mod(109+7)) and is uniquely determined. For the second query, the probability that both events 55 and 33 occurred is 0.103520.10352.

For Sample Case #2, for the first query, the probability that both events 11 and 22 occurred is given by (the probability that event 11 occurred) ×× (probability that event 22 occurs given event 11 occurred). As 11 is the parent event of event 22, the probability of event 22 occurring given event 11 occurred is A2A2 which is 0.10.1. Hence, the probability that both events 11 and 22 occurred is 0.3×0.10.3×0.1. Hence, the output will be 3×102mod(109+7)=7100000053×10−2mod(109+7)=710000005. For the second query, the probability of occurrence of both events 22 and 44 is 0.0570.057.

Leave a Comment