Postcards | Topcoder Archive

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

Definition

Class:: Postcards
Method:: count
Parameters:: int, int, int
Returns:: int
Method signature:: int count(int N, int Y, int seed)
(be sure your method is public)

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.

Examples

```
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.)
```
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.

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.