Connection Status:
Competition Arena > TreeWalker

TreeWalker

SRM 690 · 2016-05-02 · by tozangezan

SRM 690 · 2016-05-02 · by tozangezan · Graph Theory, Simple Math
Class Name: TreeWalker
Return Type: int
Method Name: calc
Arg Types: (int, int, int, int, int)
Problem Statement

Problem Statement

Given a directed graph G, we will use p(G) to denote the number of ordered pairs of distinct vertices (x,y) such that G contains a directed path from x to y.

For example, let G1 be a graph on vertices {0,1,2} that contains the edges 0->1 and 1->2. For this graph we have p(G1)=3: there is a path from 0 to 1, a path from 1 to 2, and a path from 0 to 2. Similarly, let G2 contain the edges 0->1 and 2->1. Then p(G2)=2: the only two valid paths are from 0 to 1 and from 2 to 1.

You are given an undirected tree T with N vertices. The vertices are numbered 0 through N-1. The exact format in which T is given is specified below.

We can change T into a directed graph U by replacing each undirected edge of T by one of the two possible directed edges. As there are exactly N-1 edges in T, there are exactly 2^(N-1) possible graphs U we can produce.

For each possible U compute the value p(U). Let X be the sum of those 2^(N-1) values. Compute and return the value (X modulo 1,000,000,007).

You are given the ints N, A0, B, C, and MOD. Use the pseudocode given below to generate the tree T. Watch out for integer overflow.

A[0] = A0
for i = 1 .. N-2:
	A[i] = (B * A[i-1] + C) % MOD

for i = 1 .. N-1:
	j = A[i-1] % i
	add an edge between vertices i and j

Constraints

  • N will be between 2 and 100,000, inclusive.
  • A0, B and C will be between 0 and 1,000,000,000, inclusive.
  • MOD will be between 1 and 1,000,000,000, inclusive.
Examples
0)
4
0
1
1
1000
Returns: 34

The graph T generated by our pseudocode is the path 0 - 1 - 2 - 3. There are 2^3 = 8 possible ways to assign directions to these edges: In two cases (0 -> 1 -> 2 -> 3, 0 <- 1 <- 2 <- 3) we have p(U) = 6. In four cases (0 -> 1 -> 2 <- 3, 0 -> 1 <- 2 <- 3, 0 <- 1 -> 2 -> 3, 0 <- 1 <- 2 -> 3) we have p(U) = 4. In two cases (0 -> 1 <- 2 -> 3, 0 <- 1 -> 2 <- 3) we have p(U) = 3. The sum of p(U) over all possible U is X = 6+6+4+4+4+4+3+3 = 34.

1)
10
0
0
0
1
Returns: 13824
2)
16
15
1
1
16
Returns: 917506
3)
1000
385498676
349131547
115776323
614879544
Returns: 245566366
4)
100000
111222333
444555666
777888999
123456789
Returns: 119729770

Submissions are judged against all 69 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class TreeWalker with a public method int calc(int N, int A0, int B, int C, int MOD) · 69 test cases · 2 s / 256 MB per case

Submitting as anonymous