31530번 - 새로운 AVL 트리 만들기 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 208 | 106 | 82 | 55.782% |
문제
AVL 트리는 해당 트리를 만든 Adelson-Velsky와 Landis의 이름을 딴 트리이다.
AVL 트리를 정의하기 위해 먼저 노드별로 ”균형값”을 정의한다. 어떤 노드의 균형값이란, 해당 노드의 왼쪽 서브트리의 높이를 $h_l$, 오른쪽 서브트리의 높이를 $h_r$이라고 할 때, $h_r-h_l$을 의미한다. 이때, 왼쪽 혹은 오른쪽 자식이 없다면 해당 방향의 서브트리의 높이는 $0$으로 생각한다. 원래 AVL트리는 모든 노드의 균형값이 $-1$, $0$, $1$ 중 하나이다.
MatKor 자료구조 세미나를 들은 민재는 자신의 이름도 넣어 AVLM 트리를 개발하려고 한다. 민재는 기존 AVL 트리에서 노드들의 균형값이 될 수 있는 $-1$, $0$, $1$ 중 일부만을 허용하고자 한다. 그래서 $\{-1,0,1\}$의 공집합이 아닌 부분집합 $S$를 정해, ”리프 노드를 제외한 모든 노드의 균형값이 $S$의 원소 중 하나인 트리”를 새로 정의해 AVLM 트리라는 이름을 붙였다. 이때, 리프 노드는 반드시 균형값이 $0$이므로, 이는 예외로 두었다.
집합 $S$와 AVLM 트리의 높이 $h$가 주어졌을 때, 높이 $h$로 가능한 트리의 모양이 몇 개 있는지 구해보자.
노드 하나만 존재하는 트리의 높이를 $1$이라고 생각한다.
입력
첫 번째 줄에 테스트 케이스의 개수 $T$가 주어진다. $(1\le T\le 10^6)$
각 테스트 케이스 별로 두 줄의 입력이 주어진다.
첫 번째 줄에 높이 $h$, $S$의 원소의 개수 $\lvert S \rvert$이 공백으로 구분되어 주어진다. $(1\le h\le 10^6;$ $1\le\lvert S \rvert\le 3)$
두 번째 줄에는 노드별로 가능한 균형값을 나타내는 $S$의 서로 다른 원소 $\lvert S \rvert$개가 오름차순으로 주어진다.
$S$는 $\{-1\} ,\{0\} ,\{1\} ,\{-1,0\} ,\{-1,1\} ,\{0,1\} ,\{-1,0,1\}$ 중 하나이다.
같은 테스트 케이스는 여러 번 주어지지 않는다.
출력
각 테스트 케이스 별로 한 줄에 하나씩 답을 $10^9+7$로 나눈 나머지를 출력한다.
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 20 | $h\le 3$ |
| 2 | 10 | $S=\{0\}$ |
| 3 | 10 | $S=\{-1\}$ 혹은 $S=\{1\}$ |
| 4 | 40 | $T=1$ |
| 5 | 40 | 추가적인 제한 없음 |
예제 입력 1
6 1 1 1 2 1 -1 3 2 -1 1 3 3 -1 0 1 5 3 -1 0 1 1000000 3 -1 0 1
예제 출력 1
1 1 4 15 108675 431215210
첫 번째, 두 번째, 세 번째, 네 번째 테스트 케이스의 경우 아래와 같이 $1$가지, $1$가지, $4$가지, $15$가지이다.
힌트
입력이 많은 경우 빠른 입출력을 사용하지 않으면 시간 초과가 나올 수 있다.
출처
University > 고려대학교 > MatKor Cup > 제4회 고려대학교 MatKor Cup: 2024 Winter/Spring 연습 세션 PB번
- 문제를 만든 사람: alex04, kidw0124
- 문제를 번역한 사람: tikiliki0417
- 문제를 검수한 사람: devluyten, eoaud0108, finimage, lighter, rachel2003, sshs29hanul, tlsdydaud1, utilforever, yijw0930
채점 및 기타 정보
- 예제는 채점하지 않는다.