cho.sh

잠금 패턴과 스패닝 트리

아직 제출이 없습니다시간 제한1초메모리 제한128 MB

문제

안드로이드는 스마트폰을 잠글 때 패턴을 쓴다. 흔히 쓰는 잠금 패턴은 3×3 그리드에 노드 9개로 이루어져 있다. 상현이는 보안을 더 높이려고 다음과 같은 잠금 패턴을 제공하는 앱을 만들려고 한다.

상현이가 만들 앱의 잠금 패턴은 크기가 2×2부터 m×mm \times m까지 다양하고, 인접한 노드끼리만 연결할 수 있다. 인접한 노드란 가로, 세로, 대각선 방향으로 바로 옆에 있는 노드를 말한다. 그래서 네 꼭짓점에 있는 노드는 3개와 연결되고, 나머지 노드는 많으면 8개와 연결된다.

잠금 패턴은 항상 스패닝 트리를 이루어야 한다. 스패닝 트리는 그래프의 간선을 모은 집합으로, 닫힌 루프를 포함하지 않는다. 또 임의의 두 노드 사이에 경로가 있어야 하고, m2=nm^2 = n개의 정점과 n−1n-1개의 간선으로 이루어진다. 잠금 패턴 하나에서 스패닝 트리는 여러 가지가 나올 수 있다.

그래프 GG의 스패닝 트리 개수를 구하려면 먼저 모든 정점에 v1,…,vnv_1, \dots, v_n처럼 번호를 붙인다. 그다음 행렬 T=[tij]T = [t_{ij}]를 이렇게 만든다.

  • i=ji = j이면 tijt_{ij}는 viv_i에 연결된 간선의 개수
  • i≠ji \ne j이면 viv_i와 vjv_j 사이에 간선이 있으면 −1-1, 없으면 00

스패닝 트리 개수는 TT의 여인자로 구한다.

cofactor of tij=(−1)i+jMij\text{cofactor of } t_{ij} = (-1)^{i+j} M_{ij}

여기서 MijM_{ij}는 TT에서 ii행과 jj열을 지워 얻은 (n−1)×(n−1)(n-1) \times (n-1) 행렬의 행렬식이다. ii와 jj를 어떻게 골라도 TT의 여인자는 모두 같은 값이다.

예를 들어 2×2 패턴의 행렬 TT는 다음과 같다.

T=(3−1−1−1−13−1−1−1−13−1−1−1−13)T = \begin{pmatrix} 3 & -1 & -1 & -1 \\ -1 & 3 & -1 & -1 \\ -1 & -1 & 3 & -1 \\ -1 & -1 & -1 & 3 \end{pmatrix}

i=1i = 1, j=1j = 1로 두고 여인자를 구하면 다음과 같다.

(−1)1+1M11=∣3−1−1−13−1−1−13∣=16(-1)^{1+1} M_{11} = \begin{vmatrix} 3 & -1 & -1 \\ -1 & 3 & -1 \\ -1 & -1 & 3 \end{vmatrix} = 16

따라서 2×2 패턴의 스패닝 트리는 16개다.

3×3 패턴의 행렬 TT는 다음과 같다.

T=(3−10−1−10000−15−1−1−1−10000−130−1−1000−1−105−10−1−10−1−1−1−18−1−1−1−10−1−10−150−1−1000−1−103−10000−1−1−1−15−10000−1−10−13)T = \begin{pmatrix} 3&-1&0&-1&-1&0&0&0&0 \\ -1&5&-1&-1&-1&-1&0&0&0 \\ 0&-1&3&0&-1&-1&0&0&0 \\ -1&-1&0&5&-1&0&-1&-1&0 \\ -1&-1&-1&-1&8&-1&-1&-1&-1 \\ 0&-1&-1&0&-1&5&0&-1&-1 \\ 0&0&0&-1&-1&0&3&-1&0 \\ 0&0&0&-1&-1&-1&-1&5&-1 \\ 0&0&0&0&-1&-1&0&-1&3 \end{pmatrix}

이 행렬의 여인자 값이 3×3 패턴의 스패닝 트리 개수다.

m×mm \times m 패턴에서 만들 수 있는 스패닝 트리의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 NN (1≤N≤51 \le N \le 5)이 주어진다. 다음 NN개 줄에는 테스트 케이스마다 패턴의 크기 mm이 한 줄에 하나씩 주어진다. (2≤m≤62 \le m \le 6)

출력

각 테스트 케이스마다 m×mm \times m 패턴에서 만들 수 있는 스패닝 트리의 개수를 한 줄에 하나씩 출력한다.

힌트

m=2m = 2인 패턴은 정점 4개가 서로 모두 연결된 그래프이고, 스패닝 트리는 16가지다.