선형 점화식의 아주 먼 항
레벨 E2 · 코딩 · JavaScript · 목표 시간 33분 · 게시일 2026-11-01
길이가 k인 배열 coef와 init가 주어진다. 수열 a는 a[i] = init[i] (0 ≤ i < k)이고, i ≥ k이면 다음과 같다.
a[i] = coef[0]·a[i-1] + coef[1]·a[i-2] + … + coef[k-1]·a[i-k]a[n]을 1,000,000,007로 나눈 나머지를 구하시오.
k는 1 이상 10 이하, coef와 init의 원소는 0 이상 1,000,000,006 이하, n은 0 이상 10^15 이하이다. 항을 하나씩 계산하는 방법으로는 시간 안에 끝나지 않는다. 두 수의 곱이 2^53을 넘으면 정확도가 깨지니 주의하시오.
예제
solve([1,1], [0,1], 10) solve([2], [3], 5) solve([1,1], [0,1], 1)