TreeMoving | Topcoder Archive

Problem Statement

You are given m trees. The trees are labeled T(0) through T(m-1). Each tree contains n vertices labeled 0 through n-1. A cyclic rotation of edges is the following procedure:

In each tree you choose one of its edges. Let e(i) be the edge chosen in the tree T(i).
You remove the chosen edge from the tree, producing a graph with n vertices and only n-2 edges.
For each valid i, you add the edge e(i) to the tree T(i+1). Also, you add the edge e(m-1) to the tree T(0). For example, if e(0) was an edge that connected vertices 4 and 7 in T(0), the graph T(1) will now get a new edge that connects its vertices 4 and 7.
The procedure was successful if and only if each T(i) is a tree again.

Count all possible ways in which we can successfully perform a cyclic rotation of edges. Return that count modulo (10^9 + 7). You are given the int n. You are also given the int[]s roots, a, b, and c, each with m elements. These are inputs to a pseudorandom generator that will produce the trees. In order to generate the tree T(i), we will first generate a temporary sequence X:

X[0] = c[i]
for k = 1 to n-2:
    X[k] = (a[i] * X[k - 1] + b[i]) modulo 1,000,000,007

and then we use that sequence to generate the edges of the tree:

for j = 0 to n-2:
    u[j] = (roots[i] + j + 1) modulo n
    v[j] = (roots[i] + (X[j] modulo (j + 1))) modulo n
    add the edge between u[j] and v[j] to the tree T(i)

Definition

Class:: TreeMoving
Method:: count
Parameters:: int, int[], int[], int[], int[]
Returns:: int
Method signature:: int count(int n, int[] roots, int[] a, int[] b, int[] c)
(be sure your method is public)

Notes

The author's solution does not depend on any properties of the pseudorandom generator. It would solve any input of the allowed size within the given limits.

Constraints

n will be between 2 and 300, inclusive.
roots will contain between 2 and 300 elements, inclusive.
a and roots will contain the same number of elements.
b and roots will contain the same number of elements.
c and roots will contain the same number of elements.
Each element of roots will be between 0 and n - 1, inclusive.
Each element of a will be between 1 and 1,000,000,006, inclusive.
Each element of b will be between 0 and 1,000,000,006, inclusive.
Each element of c will be between 0 and 1,000,000,006, inclusive.

Examples

```
3
```
```
{0, 2}
```
```
{1, 2}
```
```
{1, 0}
```
```
{2, 3}
```
```
Returns: 2
```
There are two trees, each of them contains 3 vertices. The tree T(0) is generated as follows: X[0] = c[0] = 2 X[1] = (a[0] * X[0] + b[0]) modulo 1,000,000,007 = 3 u[0] = (roots[0] + 1) modulo n = 1 v[0] = (roots[0] + (X[0] modulo 1)) modulo n = 0 u[1] = (roots[0] + 2) modulo n = 2 v[1] = (roots[0] + (X[1] modulo 2)) modulo n = 1 Hence, the tree T(0) contains the edges 1-0 and 2-1. The tree T(1) contains the edges 0-2 and 1-2. There are two ways to do a successful cyclic rotation of edges: we can either choose the edge 1-2 in each tree, or we can choose the edge 0-1 in T(0) and the edge 0-2 in T(1).
```
3
```
```
{0, 0, 1}
```
```
{6, 1, 3}
```
```
{6, 5, 5}
```
```
{2, 5, 9}
```
```
Returns: 2
```
T(0) contains edges 1-0 and 2-0. T(1) contains edges 1-0 and 2-0. T(2) contains edges 2-1 and 0-1.

{0, 1, 1, 1, 2}

{7, 4, 7, 9, 2}

{8, 3, 9, 5, 3}

{6, 0, 1, 5, 9}

Returns: 22

{0, 0, 1}

{373206610, 937739946, 172315864}

{870770575, 635025870, 765158489}

{915938656, 747443899, 387215442}

Returns: 2

Watch out for integer overflow when generating the temporary sequence X.

{0, 1, 0, 4, 0, 2, 1, 8, 5, 5}

{508821715, 481198414, 163209181, 56649169, 276327522, 13486359, 845629232, 482370937, 373100199, 297431939}

{256979012, 884002808, 393825387, 609998779, 816536931, 123064634, 673095376, 18224901, 510687925, 466437174}

{368733721, 596826005, 853637399, 436680590, 369153650, 853574577, 609377415, 903050702, 259325966, 105275092}

Returns: 17765

Watch out for integer overflow when calculating the answer.

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.