11272. Игра Ани

 

Маленькая девочка Аня любит играть в следующую игру.

Сначала она рисует на бумаге один круг. Затем она рисует ещё один круг и соединяет его линией с первым. После этого она рисует очередной круг и соединяет его линией с одним из уже нарисованных кругов. Анна продолжает действовать таким образом, пока не нарисует ровно n кругов, причём каждый новый круг соединяется ровно с одним из ранее нарисованных.

При этом никакие круги не пересекаются, и никакие линии не пересекаются между собой. В конце Анна нумерует все круги числами от 1 до n в произвольном порядке.

Сколько различных картинок может нарисовать Аня, содержащих ровно  кругов? Два изображения считаются различными, если существует такая пара номеров (i, j), что на одном изображении круги с номерами i и j соединены линией, а на другом – нет.

 

Вход. Первая строка содержит количество тестов t. Каждый тест состоит из одной строки, содержащей одно целое число n (0 < n ≤ 100).

 

Выход. Для каждого теста выведите строку вида “Case #x: res”, где x – номер теста, а res – остаток от деления ответа на 2000000011.

 

Пример входа

Пример выхода

3

1

2

3

Case #1: 1

Case #2: 1

Case #3: 3

 

 

РЕШЕНИЕ

графы – остовное дерево

 

Анализ алгоритма

В задаче требуется найти количество различных пронумерованных деревьев с n вершинами. Или то же самое, что нужно найти число остовных деревьев в полном графе из n вершин.

Напомним, что граф называется полным, если каждая пара его вершин соединена ребром.

 

Теорема. Существует взаимно однозначное соответствие между остовными деревьями полного графа из n вершин и кодами Прюфера длины n – 2.

 

Лемма. Количество различных кодов Прюфера длины n – 2 равно nn-2.

 

Следовательно, количество различных рисунков, которые может изобразить Аня (то есть количество пронумерованных деревьев с n вершинами), равно nn-2.

 

Пример

Для n = 4 существует 16 различных деревьев. Под каждым деревом приведён соответствующий ему код Прюфера.

(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)

 

 

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

Читаем количество тестов tests.

 

scanf("%d",&tests);

for (t = 1; t <= tests; t++)

{

 

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

 

  scanf("%d",&n);

 

Вычисляем и выводим значение nn-2 по модулю 2000000011.

 

  res = 1;

  for (i = 0; i < n - 2; i++)

    res = (res * n) % 2000000011;

  printf("Case #%d: %lld\n",t,res);

}