TreeMovingDiv2

SRM 711 · 2017-02-20 · by Arterm

SRM 711 · 2017-02-20 · by Arterm · Graph Theory, Math

Show categories

Class Name: TreeMovingDiv2

Return Type: int

Method Name: count

Arg Types: (int, vector<int>, vector<int>, vector<int>, vector<int>)

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)

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 50, inclusive.
roots will contain between 2 and 50 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}
{3, 5}
Returns: 2

There are two trees, each of them contains 3 vertices. The tree T(0) is generated as follows: X[0] = c[0] = 3 X[1] = (a[0] * X[0] + b[0]) modulo 1,000,000,007 = 4 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 = 0 Hence, the tree T(0) contains the edges 1-0 and 2-0. 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 0-2 in each tree, or we can choose the edge 0-1 in T(0) and the edge 1-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.

5
{0, 1, 1, 1, 2}
{7, 4, 7, 9, 2}
{8, 3, 9, 5, 3}
{6, 0, 1, 5, 9}
Returns: 22

2
{1, 0, 0}
{122064284, 9662111, 120616497}
{20137061, 408976122, 494878172}
{242061783, 603049107, 805670429}
Returns: 1

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

10
{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

11)

15
{11, 3, 13, 5, 0, 3, 0, 8, 9, 4, 9, 7, 5, 12, 12, 11, 12, 2, 6, 5, 13, 13, 11, 8, 14, 9, 2, 0, 3, 11, 10, 12, 10, 11, 11, 12, 13, 7, 12, 11, 2, 14, 8, 3, 6, 6, 4, 13, 5, 8}
{983816220, 620877501, 728957664, 719453482, 891241034, 959047323, 459235325, 188837384, 749336264, 40650017, 404049008, 121578182, 640967952, 444329307, 181115164, 697849277, 12923013, 711014676, 308063158, 403714366, 341206103, 674610097, 743172147, 27978413, 95548595, 93823839, 844476902, 863583697, 568069127, 618319911, 659846531, 341309147, 735202433, 531047579, 967335611, 311192666, 753647731, 36420180, 609571991, 208600401, 915548304, 926479460, 672275772, 545217041, 864561330, 32472050, 852336473, 144521601, 383750815, 616511468}
{715457951, 308091233, 686233659, 523365634, 260145657, 96581518, 754153775, 622990522, 78662953, 689973864, 609423534, 534351235, 56822117, 899080526, 236413795, 747521954, 249656307, 790813221, 238598034, 203856426, 170015231, 791645278, 991710627, 747864180, 331241135, 416320805, 820623220, 811261319, 154661650, 914880513, 270905767, 954448019, 261442212, 954262444, 293791600, 493225233, 67542211, 911866345, 567575019, 95716070, 410883122, 337767450, 375732581, 616839717, 416849487, 140196829, 200763187, 51759408, 992789421, 882490836}
{650915191, 363659051, 226659197, 706291662, 748630395, 163284394, 663006670, 2890697, 639793395, 728890798, 570088430, 967259303, 101778889, 249725396, 968816738, 276471315, 905010209, 467925249, 798793109, 857289233, 494026470, 476417587, 98570430, 596160845, 211373787, 188742439, 364805067, 757845257, 317224756, 74104796, 455729968, 78933290, 769895010, 476555278, 45379277, 957039727, 395817921, 447349376, 629724490, 287334171, 227424105, 603337884, 467060652, 254067677, 237332026, 976429932, 93075762, 960441433, 132935737, 671265490}
Returns: 755767349

Watch out for integer overflow while calculating the answer.

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

Coding Area

Language: C++17 · define a public class TreeMovingDiv2 with a public method int count(int n, vector<int> roots, vector<int> a, vector<int> b, vector<int> c) · 31 test cases · 2 s / 256 MB per case