Funcia
Lv.4divide-and-conquermathmatrix-exponentiation

아주 먼 항의 점화식 값

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

수열 a0,a1,a2,…a_0, a_1, a_2, \dots 가 다음 선형 점화식을 따릅니다. coef의 길이를 KK라 할 때,

am=coef[0]⋅am−1+coef[1]⋅am−2+⋯+coef[K−1]⋅am−K(m≥K)a_m = \texttt{coef}[0] \cdot a_{m-1} + \texttt{coef}[1] \cdot a_{m-2} + \cdots + \texttt{coef}[K-1] \cdot a_{m-K} \quad (m \ge K)

처음 KK개 항은 init으로 주어집니다(init[i] =ai= a_i).

질의 목록 queries의 각 n에 대해 ana_n을 1,000,000,0071{,}000{,}000{,}007로 나눈 나머지를 구해, 질의 순서대로 배열에 담아 반환하세요. n은 최대 101810^{18}입니다.

입출력 예

coefinitqueriesresult
[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 — 피보나치 수열입니다. a10=55a_{10} = 55이고, a50=12,586,269,025a_{50} = 12{,}586{,}269{,}025를 1,000,000,0071{,}000{,}000{,}007로 나눈 나머지는 586,268,941586{,}268{,}941입니다.

예 2 — am=2am−1+am−3a_m = 2a_{m-1} + a_{m-3}이므로 a3=2+1=3a_3 = 2 + 1 = 3, a4=6+1=7a_4 = 6 + 1 = 7, a5=14+1=15a_5 = 14 + 1 = 15입니다.

예 3 — an=2⋅3na_n = 2 \cdot 3^n입니다. 지수가 101810^{18}이어도 답을 구할 수 있어야 합니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

함수 시그니처

solution(coef: int[], init: int[], queries: long[]) → int[]

제한 사항

  • 1≤K=1 \le K = coef.length == init.length ≤30\le 30
  • 0≤0 \le coef[i], init[i] <1,000,000,007< 1{,}000{,}000{,}007
  • 1≤Q=1 \le Q = queries.length ≤1,000\le 1{,}000
  • 0≤0 \le queries[q] ≤1018\le 10^{18}

기대 복잡도

시간
O(K^3 log N + Q K^2 log N)
공간
O(K^2 log N)

입출력 예

coefinitqueries기대 출력
[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]

힌트

힌트

최근 KK개 항을 묶은 상태 벡터 vm=(am+K−1,…,am)v_m = (a_{m+K-1}, \dots, a_m)를 생각하면, 한 칸 진행은 K×KK \times K 동반 행렬 TT를 곱하는 일입니다.

T=(c0c1⋯cK−1 10⋯0 ⋱⋮ 0⋯10),vm+1=T vmT = \begin{pmatrix} c_0 & c_1 & \cdots & c_{K-1} \ 1 & 0 & \cdots & 0 \ & \ddots & & \vdots \ 0 & \cdots & 1 & 0 \end{pmatrix}, \qquad v_{m+1} = T\,v_m

따라서 ana_n은 T n−K+1v0T^{\,n-K+1} v_0의 첫 성분입니다. 거듭제곱은 분할 정복(제곱을 반복)으로 O(K3log⁡n)O(K^3 \log n)에 구합니다.

질의가 많을 때

질의마다 행렬 거듭제곱을 새로 하면 O(QK3log⁡n)O(Q K^3 \log n)으로 효율성 테스트를 넘기 어렵습니다.

  • T,T2,T4,…,T259T, T^2, T^4, \dots, T^{2^{59}}을 한 번만 미리 구해 둡니다(O(K3log⁡n)O(K^3 \log n)).
  • 각 질의는 지수의 켜진 비트마다 미리 구한 행렬을 벡터에 곱합니다. 행렬×벡터는 O(K2)O(K^2)라 질의당 O(K2log⁡n)O(K^2 \log n)입니다.

곱셈 중간값은 64비트 범위 안에서 나머지를 취하세요.

복잡도 목표

O(K3log⁡n+QK2log⁡n)O(K^3 \log n + Q K^2 \log n)이 필요합니다. 항을 하나씩 계산하는 풀이나 질의마다 행렬을 거듭제곱하는 풀이는 시간 초과가 납니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.132794 ms도출됨
Java 251042 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1400 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness4011판정만
performance603판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.