아테즈

이 문제는 A(n) = A(n-1) + A(n-2)의 선형 점화식의 항을 빠르게 구하는 것을 목표로 합니다. 게다가 n의 범위가 10^18(1,000,000,000,000,000,000)인 걸 보아 절대 동적 계획법으로는 풀 수 없는 문제입니다. 이럴 땐, 점화식을 자세히 살펴보고, 분해해보아야 합니다. 수열의 n번째 항과, n-1번째 항을 위 아래로 나열해보면 과 같이 나타낼 수 있습니다. 그럼? 이것을 행렬로 나타내보면? 입니다. 오! 개쩔죠? 그럼? 이 점화식을 계속해서 나열해본다면! 이 될 것이고 이렇게 되니까, 피보나치 수열의 일반 행렬을 얻을 수 있습니다. n by n의 행렬을 곱하는 데엔 보통 O(n^3)의 시간 복잡도가 필요합니다.그리고 같은 행렬을 M번 곱하는 데는 O(Mn^3)의 시간이..