Problem Statement
Limak is a grizzly bear. He is currently making plans to attack Deerland.
Deerland has N cities, numbered from 0 to N-1. The cities are all connected together by a network of roads. There are exactly N-1 bidirectional roads, each connecting two cities. (Hence, the topology of Deerland is a tree.)
Limak will attack each city in Deerland exactly once. For each i, when he attacks city i, there are two possible outcomes:
- With probability 1/(i+1) the city will defend itself successfully.
- In all other cases the city is destroyed by Limak. The city disappears from Deerland, along with all roads that led into the city.
Let's define a region as a connected component of Deerland. In other words, a region is a maximal group of cities such that the existing roads allow us to travel between any two cities in the group. Initially, the entire Deerland is a single region. After Limak's N attacks Deerland will be divided into one or more regions.
The strength of a region is the square of the number of cities it contains.
You are given a description of Deerland in a format that is specified below. Let E be the expected value of the sum of strengths of all regions after Limak attacks Deerland. It can be proved that E*N! is an integer. Return this integer modulo 1,000,000,007.
The description of Deerland is provided in the form of a pseudorandom generator.
You are given the
R = R0;
BILLION = 1000000000;
for i between 1 and N-1, inclusive:
R = (A * R + B) modulo M;
MIN = ((i-1) * LOW) / BILLION;
MAX = ((i-1) * HIGH) / BILLION;
there is a road between city i and city MIN + (R modulo (MAX-MIN+1));
Both divisions in the pseudocode are integer divisions. (Integer division rounds down. For example, 29/10 is 2.) You may assume that the pseudocode always generates a valid tree. Watch out for integer overflow when implementing it.
Definition
- Class:
- BearAttacks
- Method:
- expectedValue
- Parameters:
- int, int, int, int, int, int, int
- Returns:
- int
- Method signature:
- int expectedValue(int N, int R0, int A, int B, int M, int LOW, int HIGH)
- (be sure your method is public)
Constraints
- N will be between 1 and 1,000,000, inclusive.
- M will be between 1 and 1,000,000,000, inclusive.
- R0, A and B will be between 0 and M-1, inclusive.
- LOW and HIGH will be between 0 and 1,000,000,000, inclusive.
- LOW will not be greater than HIGH.
Examples
3
0
2
3
100
938593850
1000000000
Returns: 21
There are N=3 cities. The generator outputs that the two roads are 1-0 and 2-1. Hence, Deerland is the path 0-1-2. Here is what may happen: With probability (1/1) * (1/2) * (1/3) = 1/6 all three cities survive. In this case we have a single region with strength 9. With probability (1/1) * (1/2) * (2/3) = 2/6 only cities 0 and 1 survive. We have one region with strength 4. With probability (1/1) * (1/2) * (1/3) = 1/6 only cities 0 and 2 survive. Here we have two regions, each with strength 1, hence the total strength is 2. With probability (1/1) * (1/2) * (2/3) = 2/6 only city 0 survives. There is only one region and its strength is 1. Therefore, the expected sum of regions' strengths is (1/6)*9 + (2/6)*4 + (1/6)*2 + (2/6)*1 = 21/6. The correct return value is ( (21/6) * N! ) modulo 1,000,000,007, which is 21.
3
0
0
0
1
0
0
Returns: 23
Again there are three cities, but now the roads are 1-0 and 2-0. A different set of roads leads to a different answer.
6
303840291
848660283
395739574
950123456
0
1000000000
Returns: 3856
Six cities. Roads: 1-0, 2-1, 3-1, 4-3, 5-1.
1
0
0
0
1
0
0
Returns: 1
19
384038999
938592393
692854433
1000000000
300000000
600000000
Returns: 473263988
25
907283241
708592740
511252684
971876197
0
1000000000
Returns: 520260122
30
871663921
537146758
384048002
982951019
0
1000000000
Returns: 600837740
50
725842590
53523743
783815874
917800553
0
1000000000
Returns: 477624210
100
680930041
291474504
229233696
952599721
0
1000000000
Returns: 852370401
200
610771342
197779531
227190781
985389917
500000000
1000000000
Returns: 146922450
500
175487164
469976352
37493940
938313869
0
100000000
Returns: 322824075
25000
388180767
230033842
602225432
962315737
0
1000000000
Returns: 980962264
123000
791876100
263847969
590056433
989672207
0
1000000000
Returns: 660649071
400123
257580280
128959476
541347900
972112919
700000000
1000000000
Returns: 775129782
998424
125176791
275501347
192302023
918346937
0
1000000000
Returns: 600373418
977447
836042151
496986734
73193488
966808463
0
1000000000
Returns: 114302877
966497
664069454
128427878
250221686
945391861
0
0
Returns: 147171859
991819
750421979
694287360
769301
945589903
0
3000
Returns: 34377535
993195
713520152
294084985
246931688
903416749
0
50123
Returns: 182597434
979995
707580253
469192935
422344247
981566197
0
10491269
Returns: 619215836
991360
338663143
750650502
236275278
903207521
50123
100123
Returns: 513431227
951822
386042127
494581272
342888622
952015151
1000000
10000000
Returns: 123162556
964121
124069452
306973259
770415697
902811971
200000000
300000000
Returns: 81581438
975039
204635682
124350657
295315613
908702621
701333920
797656599
Returns: 3327868
990735
420996336
910622651
291198356
910949933
900000000
1000000000
Returns: 790720480
991291
48916974
647317908
748142120
944290531
505655106
1000000000
Returns: 934717618
992284
174375768
19813892
408594106
957639341
999000000
1000000000
Returns: 569876399
990198
99314055
296730184
759804319
983497897
999990000
1000000000
Returns: 807777966
979663
561333867
30159231
469324672
915548393
500000000
500000000
Returns: 429239965
982663
474635578
315062384
521517249
956092127
10000000
10000000
Returns: 196795368
961598
174462599
122349448
327592761
982467193
999000000
999000000
Returns: 260788220
988099
714948978
763736660
710306007
900451271
1000000000
1000000000
Returns: 54305831
951049
318594085
101557612
341359975
953998313
999990000
1000000000
Returns: 566874857
976727
399804259
828606630
130471160
983550233
999998000
1000000000
Returns: 361886324