아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

피보나치 수열

시간 제한2초메모리 제한512 MB

요약
x가 최대 2^48까지 커질 수 있는 최대 1000개의 질의에 대해 x번째 피보나치 수를 10^9로 나눈 나머지를 구한다.
난이도

보통10점 중 7점

유형
수학, 행렬, 분할 정복, 정수론
정답자
아직 제출이 없습니다

문제

정수 xx를 입력받아 피보나치 수열의 xx번째 값 f(x)f(x)를 10910^9으로 나눈 나머지를 구한다.

피보나치 수열의 정의는 다음과 같다.

f(1)=f(2)=1f(1) = f(2) = 1

f(k)=f(k−1)+f(k−2)(k>2)f(k) = f(k-1) + f(k-2) \quad (k > 2)

입력

첫 줄에 테스트 케이스의 개수 tt가 주어진다 (1≤t≤10001 \le t \le 1000).

이어지는 tt개의 줄에는 각각 정수 xx가 하나씩 주어진다 (1≤x≤2481 \le x \le 2^{48}).

출력

각 테스트 케이스마다 f(x)f(x)를 10910^9으로 나눈 나머지를 한 줄에 하나씩 출력한다.

예제3

  1. 예제 1

    입력
    11
1
2
8
20
46
60
3749999998
3749999999
3750000000
3750000001
281474976710656
    예상 출력
    1
1
21
6765
836311903
8755920
499999999
500000001
0
500000001
309764667

  2. 예제 2

    입력
    1
1
    예상 출력
    1

  3. 예제 3

    입력
    20
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
    예상 출력
    1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765