Funcia
Lv.4divide-and-conquermathmatrix-exponentiation

Far Terms of a Linear Recurrence

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

A sequence a0,a1,…a_0, a_1, \dots follows a linear recurrence of order KK = coef.length:

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)

with the first KK terms given by init (init[i] =ai= a_i). For each n in queries (up to 101810^{18}), return ana_n modulo 1,000,000,0071{,}000{,}000{,}007, in query order.

Examples

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]

Example 1 — Fibonacci numbers; a50=12,586,269,025≡586,268,941a_{50} = 12{,}586{,}269{,}025 \equiv 586{,}268{,}941.

Example 2 — am=2am−1+am−3a_m = 2a_{m-1} + a_{m-3} gives 3,7,153, 7, 15.

Example 3 — an=2⋅3na_n = 2 \cdot 3^n, even for n=1018n = 10^{18}.

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

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

Constraints

  • 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}

Expected complexity

Time
O(K^3 log N + Q K^2 log N)
Space
O(K^2 log N)

Examples

coefinitqueriesExpected
[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]

Hint

Hint

Advancing one step multiplies the state (am+K−1,…,am)(a_{m+K-1}, \dots, a_m) by the K×KK \times K companion matrix TT, so ana_n is the first entry of T n−K+1v0T^{\,n-K+1} v_0, computed by repeated squaring. With many queries, precompute T2bT^{2^b} once (O(K3log⁡n)O(K^3 \log n)) and answer each query with matrix-vector products (O(K2log⁡n)O(K^2 \log n) per query). A fresh matrix power per query, O(QK3log⁡n)O(QK^3 \log n), exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.132794 msderived
Java 251042 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4011verdict only
performance603verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.