Гра Ані#11272

Гра Ані (Розбір)

У задачі потрібно знайти кількість різних пронумерованих дерев з $n$ вершинами. Або так само, потрібно знайти кількість остовних дерев у повному графі з $n$ вершинами.

Нагадаємо, що граф називається повним, якщо кожна пара його вершин з'єднана ребром

Теорема. Існує взаємно однозначна відповідність між остовними деревами повного графа з $n$ вершинами та кодами Прюфера довжиною $n - 2$ n - 2.

Лема. Кількість різних кодів Прюфера довжини $n - 2$ n - 2 дорівнює $n^{n - 2}$ n^{n - 2}.

Отже, кількість різних малюнків, які може намалювати Аня (тобто кількість пронумерованих дерев з $n$ вершинами), дорівнює $n^{n - 2}$ n^{n - 2}.

Приклад

Для $n = 4$ n = 4 існує $16$ різних дерев. Під кожним деревом наведено відповідний код Прюфера.

Реалізація алгоритму

Читаємо кількість тестів $t es t s$ .

scanf("%d",&tests);
for (t = 1; t <= tests; t++)
{

Для кожного тесту читаємо значення $n$ .

  scanf("%d",&n);

Обчислюємо та виводимо значення $n^{n - 2}$ n^{n - 2} за модулем $2000000011$ .

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