숨은 점화식의 N번째 항
다이아몬드 IV의견: 0
어떤 정수 수열 \(a_0, a_1, a_2, \dots\)는 알 수 없는 차수 \(k\)의 선형 점화식
\(a_i = c_1 a_{i-1} + c_2 a_{i-2} + \dots + c_k a_{i-k} \pmod{p}\)
를 따른다(계수 \(c_j\)와 차수 \(k\)는 주어지지 않는다). 수열의 앞부분 항 \(m\)개 \(a_0, \dots, a_{m-1}\)이 주어질 때, \(a_N\)을 소수 \(p = 998{,}244{,}353\)로 나눈 나머지를 구하여라.
주어진 항들은 차수가 최대 \(m/2\)인 어떤 선형 점화식을 만족함이 보장된다.
\(N\)이 매우 크므로 항을 하나씩 계산할 수 없다.
\(2 \le m \le 500\)
\(0 \le N \le 10^{18}\)
\(0 \le a_i < p\)
주어진 항들은 차수 \(\le m/2\)인 선형 점화식을 만족한다.
첫 줄에 주어지는 항의 개수 \(m\)과 구하고자 하는 인덱스 \(N\)이 주어진다.
둘째 줄에 \(a_0, a_1, \dots, a_{m-1}\)이 공백으로 구분되어 주어진다 (각 값은 이미 \(p\)로 나눈 나머지).
\(a_N \bmod p\)를 한 줄에 출력한다.
10 20
0 1 1 2 3 5 8 13 21 34
6765주어진 10개 항은 피보나치 수열 \(a_i=a_{i-1}+a_{i-2}\)이다. 벌레캄프-매시로 점화식 [1, 1]을 복원하고 \(a_{20}=6765\)를 얻는다.
6 10
3 6 12 24 48 96
3072항들은 \(a_i = 2a_{i-1}\), \(a_0=3\)인 등비수열이다. 점화식 차수 1을 복원해 \(a_{10} = 3 \cdot 2^{10} = 3072\)를 얻는다.
riseoj 작성
출처 Original
평가 및 의견
숨은 점화식의 N번째 항
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
숨은 점화식의 N번째 항