아이디어

• 다음 행렬식을 사용한다. ($\{F_n\}$은 피보나치 수열)
  $\begin{bmatrix} F_{n+1} & F_{n} \\ F_{n} & F_{n-1} \end{bmatrix}=\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n$
• 거듭제곱은 분할 정복 방식으로 구현한다.
• 합과 곱은 모듈로를 적용해야함에 주의한다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer tk = null;

	static int[][] C = new int[2][2];
	static int[][] T = new int[2][2];
	
	static final int[][] F = {{1, 1}, {1, 0}};
	static final int MOD = 1_000_000_007;
	
	public static void main(String[] args) throws Exception {
		long n = Long.parseLong(rd.readLine());
		pow(F, n, C);
		System.out.println(C[0][1]);
	}
	
	static int add(int a, int b) {
		return (a + b) % MOD;
	}
	
	static int times(int a, int b) {
		return (int) (((long) a*b) % MOD);
	}
	
	static void copy(int[][] t, int[][] c) {
		c[0][0] = t[0][0];
		c[0][1] = t[0][1];
		c[1][0] = t[1][0];
		c[1][1] = t[1][1];
	}
	
	static void mult(int[][] a, int[][] b, int[][] c) {
		T[0][0] = add(times(a[0][0], b[0][0]), times(a[0][1], b[1][0]));
		T[0][1] = add(times(a[0][0], b[0][1]), times(a[0][1], b[1][1]));
		T[1][0] = add(times(a[1][0], b[0][0]), times(a[1][1], b[1][0]));
		T[1][1] = add(times(a[1][0], b[0][1]), times(a[1][1], b[1][1]));
		copy(T, c);
	}
	
	static void pow(int[][] a, long n, int[][] c) {
		if (n == 1) {
			copy(a, c);
			return;
		}
		pow(a, n/2, c);
		mult(c, c, c);
		if (n % 2 == 1)
			mult(c, a, c);
	}
}
}

메모리 및 시간

• 메모리: 14292 KB
• 시간: 124 ms

리뷰

• 수학 문제 주제에 구현이 더 귀찮은 문제
• 오늘부터 다시 PS 재활치료 시작
• 수정) 이 문제와 비슷한 2749번: 피보나치 수 3은 피사노 주기를 사용하여 풀 수도 있다고 한다. 이 버전은 피사노 주기를 사용할 수 없는 버전이다.