UVa 10843

From Algorithmist
Jump to: navigation, search

10843 - Anne's game[edit]

Summary[edit]

For this problem, we have to find the number of labeled trees on N vertices, modulo 2000000011.

Explanation[edit]

Each circle is a vertex and each line drawn is an edge. Clearly after N steps we have a connected graph with N vertices and N-1 edges. Thus the resulting graph is a tree. It can be proved that there are exactly N^{{N-2}} labeled trees on N vertices. Since we only have to print the answer modulo 2000000011, this can be safely calculated without the use of BigNum.

Implementation[edit]

While the answer fits into a 32-bit signed integer, using 64-bit integers is recommended when computing the result to avoid overflow.

Notes[edit]

The answer can be computed in O(\log n) time using Repeated Squaring.

An exceptionally nice proof that the number of labeled trees on N vertices is N^{{N-2}} can de achieved using the Prufer code of a tree.

Input[edit]

3
1
2
3

Output[edit]

Case #1: 1
Case #2: 1
Case #3: 3