1053 : 피보나치
- 제한시간
- 1000 ms
- 메모리제한
- 64 MB
- 해결횟수
- 585 회
- 시도횟수
- 1194 회
문제
피보나치 정수 수열에서 F0 = 0, F1 = 1 이다. 그리고 모든 n ≥ 2 에 대하여 다음과 같이 정의 된다 Fn = Fn-1 + Fn-2 .
예를 들어 피보나치수열의 처음 몇 항들은 : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 … 이다.
피보나치수열의 다른 공식은 다음과 같다.
주어진 정수 n에 대하여 당신이 할 일은 피보나치수열 Fn의 마지막 4자리수를 구하는 것이다.
입력형식
입력은 여러 개의 test case를 포함할 수 있다.
각 test case는 한 줄에 n (0 ≤ n ≤ 1,000,000,000)을 포함한다.
입력의 끝은 −1을 포함한 한 줄로 주어진다.
출력형식
각 test case에 대해 ,Fn의 마지막 4자리수를 출력한다. (이를테면 Fn을 10,000 으로 나눈 나머지를 출력한다).
만약 마지막 네 자리가 모두 0 이라면 '0' 을 출력한다. 그렇지 않다면, 모든 leading zero는 제거한다.
입력 예0 9 999999999 1000000000 -1 |
출력 예0 34 626 6875 |
Hint!
행렬 곱셈은 결합연산이 가능하며 두 2행 2열 행렬의 곱은 아래와 같다:
또 어떤 2행 2열 행렬에 대해서도 행렬의 0승은 단위행렬과 같다.
주 : 단위행렬 이란 A * I = I * A = A 일 경우 I 를 단위행렬이라고 한다.
분할정복