Spanning Trees in a Secure Lock Pattern
Блокировка экрана на смартфоне может быть реализована с помощью рисунка. Рисунок для разблокировки имеет 9 вершин на сетке 3×3. В этой задаче мы изменим размер сетки, позволив ему меняться от 2×2 до m×m, и только ограниченное количество соединений разрешено между парами соседних вершин. Назовем такой модифицированный сетевой граф G, V - множество его вершин, E - множество ребер (соединений). Примеры сетевых графов 2×2, 3×3 и 4×4 приведены на рисунках. Угловые вершины имеют не более 3 соединений, а центральные до 8 соединений. Разрешены соединения только между соседними вершинами.
Определим остовное дерево как набор ребер графа, не образующих цикл, и по которым можно пройти между любыми двумя вершинами. Остовное дерево содержит m^2 = n вершин и n – 1 ребро. Остовные деревья в графе могут иметь различные виды и формы.
Для вычисления количества остовных деревьев в G, обозначим вершины G метками v_1, ..., v_n. Образуем метрицу n×n дерева T = [t_ij] следующим образом.
Если i = j, то t_ii равно числу смежных ребер с v_i в G.
Если i ≠ j, то t_ij = 0 если не существует ребра между v_i и v_j в G.
Если i ≠ j, то t_ij = -1 если существует ребро между v_i и v_j в G.
Тогда количество остовных деревьев в G равно
cofactor of a_ij = (-1)^{i+j}M_ij
где M_ij - детерминант матрицы (n-1) × (n-1) полученной удалением строки i и столбца j из матрицы дерева T. Значение любого алгебраического дополнения T дает один и тот же результат.
Пример 1: Матрица дерева T для сетевого графа 2×2 равна
Вычислим алгебраическое дополнение T. Например, исключив строку 1 и столбец 1, получим
Поэтому количество остовных деревьев равно 16.
Пример 2: Матрица дерева T сетевого графа 3×3 имеет вид
Значение любого алгебраического дополнения T одно и то же и равно количеству остовных деревьев.
Подсказка: Вычислить определитель можно используя элементарные операции над строками:
Следует преобразовать начальную матрицу к верхней треугольной (все элементы ниже главной диагонали равны нулю). Преобразуйте матрицу строка за строкой используя элементарные операции на строках, вследствие чего все элементы ниже главной диагонали станут нулевыми. Затем перемножьте элементы главной диагонали и получите значение определителя.
Напишите программу, которая вычислит количество остовных деревьев для модифицированного сетевого графа размера m×m.
Входные данные
Первая строка содержит количество тестов n (1 ≤ n ≤ 5). Каждый тест содержит одно целое число m (2 ≤ m ≤ 6) - размер mxm сетки - графа.
Выходные данные
For each test case, your program should output the number of spanning trees, which indicates how many patterns of spanning trees there are for a given modified mesh graph. Print out one line per test case, respectively.
Примеры
Примечание
В примере имеется только один тест (n = 1). Для первого теста при m = 2 имеется 16 различных остовных деревьев. Все они перечислены ниже. Вашей программе НЕ требуется рисовать все изображения.
