25122번 - 부분배열 점수 구하기 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1.5 초 (하단 참고) | 512 MB | 21 | 12 | 12 | 63.158% |
문제
Alice는 정수 배열을 이용한 놀이를 즐겨한다.
길이 $n$인 정수 배열 $A$가 있을 때 $i$번째 원소를 $A[i]$라 하자 ($i = 1, 2, \dots, n$). 이때 $A$의 부분배열 $A[i, j]$는 $i$번째 원소부터 $j$번째 원소까지를 포함한 길이 $(j - i + 1)$인 배열로 정의한다 ($1 ≤ i ≤ j ≤ n$). 예를 들어 $A = [1, 3, 5, 7]$이라면 $A[1, 2]$은 $[1, 3]$이고 $A[2, 4]$은 $[3, 5, 7]$이 된다. 참고로 $A$의 부분 배열은 총 $n \times (n+1) / 2$개 존재한다.
각각의 부분배열 $A[i, j]$에 대하여 Alice는 아래와 같은 방법으로 점수를 매기기로 했다. 편의상 $A[i, j]$의 점수를 $Score(i, j)$라 하자. ($1 ≤ i ≤ j ≤ n$)
- [규칙 1] 만약 $i = j$ 라면 $Score(i, j) := 0$이다.
- [규칙 2] 만약 $i < j$ 이고 $A[i, j]$의 원소 중 중복된 값이 있다면 $Score(i, j) := 0$ 이다.
- [규칙 3] 만약 $i < j$ 이고 $A[i, j]$의 원소 중 중복된 값이 없다면 $Score(i, j) := i^{(j - i + 1)} + j^{(j - i + 1)}$ 이다.
예를 들어 $A = [1, 1, 2]$ 인 경우를 살펴보자.
- 규칙 1에 따라 $Score(1, 1) = Score(2, 2) = Score(3, 3) = 0$ 이다.
- 규칙 2에 따라 $Score(1, 2) = Score(1, 3) = 0$ 이다. 두 경우 모두 부분 배열에 $1$이 한 번 이상 포함되기 때문이다.
- 규칙 3에 따라 $Score(2, 3) = 2^2 + 3^2 = 13$이다.
다른 예로, $A = [1, 3, 5, 7]$ 인 경우를 살펴보자.
- 규칙 1에 따라 $Score(1, 1) = Score(2, 2) = Score(3, 3) = Score(4, 4) = 0$이다.
- 규칙 2에 해당하는 부분 배열은 없다.
- 규칙 3에 따라 길이 $2$ 이상의 모든 부분 배열의 점수를 구하면 아래와 같다:
- $Score(1, 2) = 1^2 + 2^2 = 5$
- $Score(2, 3) = 2^2 + 3^2 = 13$
- $Score(3, 4) = 3^2 + 4^2 = 25$
- $Score(1, 3) = 1^3 + 3^3 = 28$
- $Score(2, 4) = 2^3 + 4^3 = 72$
- $Score(1, 4) = 1^4 + 4^4 = 257$
정수 배열 $A$가 주어졌을 때, Alice를 도와 $A$의 부분배열 점수 총합을 구해보자.
입력
첫 줄에 테스트 케이스의 수 $T$가 주어진다.
각 테스트 케이스의 첫 줄에는 배열의 길이 $n$이 주어지고 둘째 줄에는 $A$의 원소인 $n$개의 정수가 공백으로 구분되어 주어진다.
출력
각 테스트 케이스의 정답을 각 줄에 출력한다. 단, 답이 매우 커질 수 있으므로 정답을 $10^9+7$로 나눈 나머지를 출력한다.
서브태스크 1 (10점)
- 1 ≤ T ≤ 10
- 2 ≤ n ≤ 1,500
- 1 ≤ A[i] ≤ 300,000
서브태스크 2 (20점)
- 1 ≤ T ≤ 10
- 2 ≤ n ≤ 100,000
- 1 ≤ A[i] ≤ 300,000
예제 입력 1
4 3 1 1 2 4 1 3 5 7 6 1 2 3 1 3 2 6 1 2 3 2 3 1
예제 출력 1
13 400 525 453
시간 제한
- Java 8: 3 초
- Python 3: 4 초
- PyPy3: 4 초
- Java 8 (OpenJDK): 3 초
- Java 11: 3 초
- Kotlin (JVM): 3 초
- Java 15: 3 초
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호