BearAttacks
SRM 664 · 2015-06-30 · by Errichto
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.
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.
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
Submissions are judged against all 34 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BearAttacks with a public method int expectedValue(int N, int R0, int A, int B, int M, int LOW, int HIGH) · 34 test cases · 2 s / 256 MB per case