Anne's game#11272

Anne's game (Editorial)

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$ n - 2.

Lemma. The number of distinct Prüfer codes of length $n - 2$ n - 2 is $n^{n - 2}$ n^{n - 2}.

Therefore, the number of different pictures that Anya can draw (that is, the number of labeled trees with $n$ vertices) is equal to $n^{n - 2}$ n^{n - 2}.

Example

For $n = 4$ n = 4, there are $16$ different trees. Below each tree, the corresponding Prüfer code is shown.

Algorithm implementation

Read the number of test cases $t es t s$ .

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 $n^{n - 2}$ n^{n - 2} modulo $2000000011$ .

  res = 1;
  for (i = 0; i < n - 2; i++)
    res = (res * n) % 2000000011;
  printf("Case #%d: %lld\n",t,res);
}