문제 링크: https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 수학, 선형대수학, 행렬 거듭제곱 백준 2749번 피보나치 수 3 문제랑 풀이가 똑같습니다. (점화식 -> 행렬 거듭제곱) https://seokjin2.tistory.com/11 [백준 2749번] 피보나치 수 3 문제 링크: https://www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 수학,..

문제 링크: https://www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 수학, 선형대수학, 행렬 거듭제곱 n이 매우 크기 때문에 dp를 이용한 점화식 풀이는 O(N)이므로 해결할 수 없다 따라서 점화식을 행렬로 변환해서 O(M^3 * logN) 시간 복잡도의 빠른 행렬 거듭제곱 알고리즘을 사용해야 한다. (이 문제는 피사노 주기도 사용 가능) 위와 같은 피보나치 수 점화식을 아래와 같이 행렬로 표현할 수 있다. 이렇게 행렬을 구하면 다음 아래의 행렬을 계산해서 c + d를 하면 Fn+1을 구할 수 있다. Fn을 구하기 위해서 다음식의 ..