Fibonacci

프로그램 명: stanford_fibo

제한시간: 1 초

피보나치 수열은 F0 = 0, F1 = 1, and Fn = Fn - 1 + Fn - 2 for n ≥ 2.

예로 처음 10 개의 항을 보면 ,

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

n 이 주어질 때 Fn 의 마지막 네 숫자를 출력하는 것이 문제이다.

여러개의 테스트 데이터가 입력으로 주어진다.

각 테스트 데이터는 한 줄에 n 이 주어진다.0 ≤ n ≤ 1,000,000,000 입력의 끝은 -1 이다.

테스트 케이스 별 출력은 Fn 의 마지막 네 숫자를 출력한다. 만약 마지막 네자리 숫자가 모두 0 이면 '0' 을 그렇지 않으면 선두에 오는 0 을 제외하고 출력한다.(즉 , Fn 을 10000 으로 나눈 나머지를 출력)

행렬의곱에서의 결합 법칙(associative)은 성립하고 , 2 * 2 행렬의 곱셈은 아래와 같이 수행 된다.

2*2 행렬의 0 거듭제곱은 단위행렬이다.

출처: Stanford Local 2006