Lv.4divide-and-conquermathmatrix-exponentiation
아주 먼 항의 점화식 값
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
수열 가 다음 선형 점화식을 따릅니다. coef의 길이를 라 할 때,
처음 개 항은 init으로 주어집니다(init[i] ).
질의 목록 queries의 각 n에 대해 을 로 나눈 나머지를 구해, 질의 순서대로 배열에 담아 반환하세요. n은 최대 입니다.
입출력 예
| coef | init | queries | result |
|---|---|---|---|
[1, 1] | [0, 1] | [10, 0, 1, 50] | [55, 0, 1, 586268941] |
[2, 0, 1] | [1, 1, 1] | [3, 4, 5] | [3, 7, 15] |
[3] | [2] | [0, 1, 1000000000000000000] | [2, 6, 492673366] |
입출력 예 설명
예 1 — 피보나치 수열입니다. 이고, 를 로 나눈 나머지는 입니다.
예 2 — 이므로 , , 입니다.
예 3 — 입니다. 지수가 이어도 답을 구할 수 있어야 합니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(coef: int[], init: int[], queries: long[]) → int[]
제한 사항
-
coef.lengthinit.length -
coef[i],init[i] -
queries.length -
queries[q]
기대 복잡도
- 시간
- O(K^3 log N + Q K^2 log N)
- 공간
- O(K^2 log N)
입출력 예
| coef | init | queries | 기대 출력 |
|---|---|---|---|
[1,1] | [0,1] | [10,0,1,50] | [55,0,1,586268941] |
[2,0,1] | [1,1,1] | [3,4,5] | [3,7,15] |
[3] | [2] | [0,1,1000000000000000000] | [2,6,492673366] |
힌트
힌트
최근 개 항을 묶은 상태 벡터 를 생각하면, 한 칸 진행은 동반 행렬 를 곱하는 일입니다.
따라서 은 의 첫 성분입니다. 거듭제곱은 분할 정복(제곱을 반복)으로 에 구합니다.
질의가 많을 때
질의마다 행렬 거듭제곱을 새로 하면 으로 효율성 테스트를 넘기 어렵습니다.
- 을 한 번만 미리 구해 둡니다().
- 각 질의는 지수의 켜진 비트마다 미리 구한 행렬을 벡터에 곱합니다. 행렬×벡터는 라 질의당 입니다.
곱셈 중간값은 64비트 범위 안에서 나머지를 취하세요.
복잡도 목표
이 필요합니다. 항을 하나씩 계산하는 풀이나 질의마다 행렬을 거듭제곱하는 풀이는 시간 초과가 납니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 2794 ms | 도출됨 |
| Java 25 | 1042 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 11 | 판정만 |
| performance | 60 | 3 | 판정만 |