171. 10830(피보나치 수 6) - 자바

import java.util.*;
import java.io.*;

class Main {
	static int p = 1000000007;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		long N = sc.nextLong();

		long[][] first = { { 1, 1 }, { 1, 0 } };

		System.out.println(pow(first, N)[0][1]);

	}

	private static long[][] pow(long[][] A, long B) {
		if (B == 1) {
			int l = A.length;
			for (int i = 0; i < l; i++) {
				for (int j = 0; j < l; j++) {
					A[i][j] %= p;
				}
			}
			return A;
		}

		long[][] tmp = pow(A, B / 2);

		if (B % 2 == 1) {
			return matrixMul(matrixMul(tmp, tmp), A);
		} else {
			return matrixMul(tmp, tmp);
		}
	}

	private static long[][] matrixMul(long[][] A, long[][] B) {
		int l = A.length;
		long[][] C = new long[l][l];
		for (int i = 0; i < l; i++) {
			for (int j = 0; j < l; j++) {
				for (int k = 0; k < l; k++) {
					C[i][j] += A[i][k] * B[k][j];
					C[i][j] %= p;
				}
			}
		}
		return C;
	}
}

문제요약

피보나치 수열을 구하라 (분할정복을 이용해서)

설명

이 문제의 핵심은 행렬의 거듭제곱을 통해서 피보나치 수열을 구할 수 있다는 것이다.

위 식을 보면 규칙이 보일 것이다.

이 놈의 거듭제곱의 형태의 [0 , 0]이, [0 , 1]과 [1 , 0]이, [1 , 1]이 피보나치 수열을 이루고 있다.

우리는 0, 1, 1, 2, 3, 5 ... 식으로 피보나치 수열을 구한다.

따라서 [0, 1]과 [1, 0] 번째가 본래 처음부터의 피보나치 수열을 나타낸다.

 

결과적으로 점화식은 다음과 같을 것이다.

각 코드의 상세정보는 

https://smhope.tistory.com/450?category=1058419 

170. 10830(행렬 제곱) - 자바

를 참고하면 된다