Postcards
SRM 840 · 2022-10-24 · by misof
Problem Statement
There are N cities in Absurdistan. They are numbered from 0 to N-1.
For simplicity, we will assume that city x has exactly (x+1) inhabitants.
Initially, no two cities were connected by roads. Then there was a Y-year period of road construction.
During this period, two cities become reachable from each other as soon as there exists a sequence of one or more roads that allows you to travel between them.
The years of the road construction period were numbered from 0 to Y-1. For each year x:
- During July of year x exactly one new road was constructed: a bidirectional road connecting the cities A[x] and B[x].
- Then, during December of year x each inhabitant of the country sent a Christmas postcard to each other inhabitant. All postcards that could reach their destination were delivered. All postcards that could not be delivered were burned by the post office.
Count the total number of delivered postcards during these Y years. Return that count modulo 10^9 + 7.
In order to keep the input small, the arrays A and B are generated pseudorandomly. Please use the following pseudocode to generate them:
state = seed
for i = 0 to Y-1:
state = (state * 1103515245 + 12345) modulo 2^31
A[i] = state modulo N
state = (state * 1103515245 + 12345) modulo 2^31
B[i] = state modulo N
Notes
- It is possible that in some years the new road will connect two cities that already were (directly or indirectly) connected. It is also possible that in some years the new road will connect a city to itself. In both cases there will be no changes to reachability between cities.
- The reference solution does not depend on the input being pseudorandom.
Constraints
- N will be between 1 and 10^9, inclusive.
- Y will be between 1 and 150,000, inclusive.
- seed will be between 0 and 2^31 - 1, inclusive.
7 1 47 Returns: 112
There is only one year. In July the people build a road that connects city 5 to itself. In December the people send postcards. As no two distinct cities are reachable, only postcards within each city will be delivered.
7 1 42 Returns: 122
This time the only road built connects cities 4 and 0. Compared to the previous example, the postcards sent from city 0 to city 4 or vice versa will also get delivered. This gives us an extra 10 postcards.
7 2 100 Returns: 348
The first road connects cities 0 and 6. Once this road is built a total of 126 postcards will be delivered. The second road then connects cities 5 and 6. During the second Christmas season the number of delivered postcards will be 222. (Don't forget about postcards between cities 0 and 5. These can now be delivered too.)
987654321 150000 47 Returns: 783886815
7654321 150000 4747 Returns: 511254732
7 20 100 Returns: 11942
Here is the full list of all 20 rows in the order in which they are built: 0-6, 6-5, 3-1, 3-3, 0-4, 6-3, 5-3, 1-6, 3-1, 3-2, 3-1, 4-5, 2-5, 6-4, 0-6, 3-6, 3-4, 1-4, 0-4, 1-1 In this test case Absurdistan eventually reaches the situation where in December all postcards get delivered: each of the 28 inhabitants of Absurdistan is able to reach each of the 27 other ones.
123 123 123 Returns: 410499337
The exact total is 1,410,499,344. Remember to compute and output it modulo 10^9 + 7.
Submissions are judged against all 116 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Postcards with a public method int count(int N, int Y, int seed) · 116 test cases · 2 s / 256 MB per case