선형 점화식의 N번째 항
플래티넘 V의견: 0
차수 \(d\) 의 선형 점화식이 다음과 같이 정의된다.
$$ f_n = c_1 f_{n-1} + c_2 f_{n-2} + \dots + c_d f_{n-d} \quad (n \ge d) $$
계수 \(c_1, \dots, c_d\) 와 초기값 \(f_0, f_1, \dots, f_{d-1}\) 이 주어질 때, \(f_N\) 을 \(1{,}000{,}000{,}007\) 로 나눈 나머지를 구하여라.
\(N\) 이 최대 \(10^{18}\) 까지 가능하므로, \(d \times d\) 동반 행렬(companion matrix)의 빠른 거듭제곱으로 \(O(d^3 \log N)\) 에 해결해야 한다. \(N < d\) 이면 \(f_N\) 은 초기값으로 직접 주어진다.
\(1 \le d \le 10\)
\(0 \le N \le 10^{18}\)
\(0 \le c_i \le 10^9\)
\(0 \le f_i \le 10^9\)
첫째 줄에 차수 \(d\) 와 정수 \(N\) 이 주어진다.
둘째 줄에 계수 \(c_1, c_2, \dots, c_d\) 가 주어진다.
셋째 줄에 초기값 \(f_0, f_1, \dots, f_{d-1}\) 이 주어진다.
\(f_N \bmod 1{,}000{,}000{,}007\) 을 출력한다.
2 10
1 1
0 1
55\(d=2\), \(c_1=c_2=1\), \(f_0=0, f_1=1\) 인 피보나치이다. \(f_{10}=55\).
3 5
1 1 1
0 1 2
11\(d=3\), \(f_n = f_{n-1}+f_{n-2}+f_{n-3}\), 초기값 \(0,1,2\). \(f_3=3, f_4=6, f_5=11\) 이다.
riseoj 작성
출처 Original
평가 및 의견
선형 점화식의 N번째 항
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
선형 점화식의 N번째 항