Ticket Price Total

This problem was created by Clive Fraser - many thanks!

The kingdom of Erehwon has a population spread over a large number of villages. The government has created a road network to connect all of the villages. Because road building is expensive there are no unnecessary roads. Although it is possible to travel by road between any pair of villages there will always be just one route between them. Many of the villages are in lowland areas, where road building is relatively easy. Other villages are in the mountains close to valuable mineral deposits or are situated in important mountain passes.

There are very few private vehicles on the roads. Trucks are used to carry goods and there is a reliable subsidised state bus network for public transport. A ticket can be purchased for a journey between any pair of villages. Although the bus system is subsidised by the state, passengers are required to pay an amount which is used to help with maintenance of the roads. There are only 10 different ticket prices, ranging from 1 to 10 currency units. The higher prices are charged when the journey passes through areas where road building and maintenance are more expensive.

Each of the villages is given a rating between 1 and 10. This rating reflects the cost of road maintenance in the area of the village. The cost of a journey between village A and village B is just the highest rating of all villages along the route, including the villages A and B themselves.

In this problem you are asked to consider every possible journey between pairs of villages and to find the sum of the ticket prices for all possible journeys. A journey from village A to village B is counted as different from the journey from village B to village A; although it is clear that the ticket costs will be the same. The start and destination villages for a journey must be different. The example described below should make things clearer.

There will be N villages, numbered from 0 to N-1. Village 0 has a rating of 1. The ratings of the remaining villages and the layout of the road network constitute a large amount of data. We will use a random number generator to create this. The Linear Congruential Generator has been used before in Code Abbey problems. A random value X(n) is generated using the formula:

X(n) = (A * X(n-1) + C) % M

In this problem we will use the values A = 445, C = 700001 and M = 2097169. Note that % M means the remainder after dividing by the modulus value of M. The value X(n-1) is the previous random value generated by this expression. In order to generate the first random value X(1) we need to be given a value for X(0) which is called the seed for the generator. This value will be supplied as part of the data for the problem.

The data values created by the generator are too large for this problem, so we will modify each random value X(n) to get a new random value R or S as follows:

To create a village rating in the range 1 to 10 we will use

R = 1 + X(n) % 262144

R is simply the remainder after dividing by 262144 so these random values will all lie in the range 1 to 262144 inclusive. Next we need to convert this value into a rating in the range 1 to 10. However, there are very few villages in such demanding terrain that the village rating is 10. The most common village rating is 1. As the rating increases the number of villages with this rating decreases. We need a fairly simple way of deriving a rating which behaves in this way. The following recursive method is used to convert R to a village rating r.

Step 1  Set the rating r to 1.
Step 2  If R is NOT divisible by 4 keep the rating r and STOP.
Step 3  Increase the rating by 1 and divide the value of R by 4.
Step 4  Return to Step 2 with the new values of R and r.

To generate a road section which connects village V to the road network we will use

S = X(n) % V

Here V is the number of the village to be added to the network. The expression for S gives a number in the range 0 to V-1 inclusive. This is the number of the village to which village V is connected by a section of road.

Consider the following very small example, where N = 5 and the random seed is 2039515. We will use the generator to create 8 random values. For each of the villages numbered 1 to 4 we will use one random number to create the village rating and then a second random number to create the road section linking the village to the network. The first 8 random numbers generated are 7209999, 1874120, 10139, 1017518, 507007, 1921033, 2011903, 505673. After converting these to r and S values, we get:

[3,0], [2,0], [4,1], [5,1]   where each pair represents [r,S]

We interpret these numbers as follows: Village 1 has a rating of 3 and is connected by a road section to village 0. Village 2 has a rating of 2 and is connected to village 0. Village 3 has a rating of 4 and is connected to village 1. Village 4 has a rating of 5 and is connected to village 1. The rating of 3 for village 1 was calculated as follows:

X(n) = 209999
R = 1 + X(n) % 262144 = 210000
r = 1
R is divisible by 4
So R = R/4 = 52500  and  r becomes 2
R is divisible by 4
So R = R/4 = 13125  and  r becomes 3
R is NOT divisible by 4 so the value of r is 3

With 5 villages there are 20 possible journeys. These are listed in the table below. The route is simply a list of the village ratings along the journey. This makes it easy to pick out the ticket cost.

Start   Destination Route       Cost
  0          1          [1, 3]   3
  0          2          [1, 2]   2
  0          3           [1, 3, 4]   4
  0          4           [1, 3, 5]   5
  1          0          [3, 1]   3
  1          2       [3, 1, 2]   3
  1          3          [3, 4]   4
  1          4          [3, 5]   5
  2          0          [2, 1]   2
  2          1       [2, 1, 3]   3
  2          3        [2, 1, 3, 4]   4
  2          4        [2, 1, 3, 5]   5
  3          0       [4, 3, 1]   4
  3          1          [4, 3]   4
  3          2        [4, 3, 1, 2]   4
  3          4       [4, 3, 5]   5
  4          0           [5, 3, 1]   5
  4          1          [5, 3]   5
  4          2        [5, 3, 1, 2]   5
  4          3       [5, 3, 4]   5

The sum of the ticket costs for this small example is 80. In the actual problem you will have a much larger number of villages but the village ratings and road connections are generated in the same way. The number of villages will not be greater than 4 x 10^5.

Input/Output description: The first and only line of the input data will consist of 2 space-separated integers X(0) and N, corresponding to the random seed and the number of villages. Your answer is a single integer, the sum of the ticket costs for all possible journeys, as described above.

Example 1:

input:
2039515 5

answer:
80

Example 2:

input:
598871 2000

answer:
10165478

Example 3:

input:
631822 329586

answer:
331471991784