11272. Anne’s game
A little girl named Anya likes to play the
following game.
First, she draws one circle on a sheet of
paper. Then she draws another circle and connects it to the first one with a
line. After that, she draws a new circle and connects it with a line to one of
the previously drawn circles. Anya continues in this way until she has drawn
exactly n circles, and each new circle is connected to exactly one of
the circles drawn earlier.
No circles ever intersect, and no lines
intersect with each other. Finally, Anya numbers all the circles from 1 to n
in an arbitrary order.
How many different pictures containing
exactly circles can Anya draw? Two pictures are considered different
if there exists a pair of numbers (i, j) such that in one picture
the circles numbered i and j are connected by a line, while in
the other picture they are not.
Input. The
first line contains the number of test cases t. Each test case consists of a single line containing one integer n (0 < n
≤ 100).
Output. For each test case, print a line of the form “Case #x: res”, where x is the test case number and res is the remainder of the answer modulo 2000000011.
|
Sample
input |
Sample
output |
|
3 1 2 3 |
Case #1: 1 Case #2: 1 Case #3: 3 |
SOLUTION
graphs – spanning tree
Algorithm analysis
The problem asks to
determine the number of different labeled trees with n vertices. Equivalently,
this is the number of spanning trees in the complete graph with n vertices.
Recall that a graph is
called complete if every pair of its vertices is connected by an
edge.
Theorem. There exists a
one-to-one correspondence between the spanning trees of the complete graph with n vertices and Prüfer
codes of length n – 2.
Lemma. The number of distinct
Prüfer codes of length n – 2 is nn-2.
Therefore, the number of
different pictures that Anya can draw (that is, the number of labeled trees
with n
vertices) is equal to nn-2.
Example
For n = 4, there are 16 different
trees. Below each tree, the corresponding Prüfer code is shown.
(1, 1) (1, 2) (1, 3) (1, 4)
(2, 1) (2, 2) (2, 3) (2, 4)
(3, 1) (3, 2) (3, 3) (3, 4)
(4, 1) (4, 2) (4, 3) (4, 4)
Algorithm implementation
Read the number of test
cases tests.
scanf("%d",&tests);
for (t = 1; t <= tests; t++)
{
For each test case, read
the value n.
scanf("%d",&n);
Compute and print the value nn-2 modulo 2000000011.
res = 1;
for (i = 0; i
< n - 2; i++)
res = (res * n) % 2000000011;
printf("Case
#%d: %lld\n",t,res);
}