문제
최대 2 칸 까지 오를 수 있을 때 오르는 방법의 가짓수를 생각해 보자.
아래 그림은 n 이 4 인 경우의 예 이다.
총 5가지 경우가 존재한다.
그렇다면 계단의 수가 n개일 때는 경우의 수가 몇가지 존재할까? 답이 커질 수 있으므로 답을 1,000,000,007로 나눈 나머지를 출력한다.
입력
입력의 첫 줄은 계단의 갯수 (1 <= N <= 1,000,000,000)이 주어진다.
출력
계단 N개를 오를 수 있는 경우의 수를 10억 7로 나눈 나머지를 출력한다.
힌트
예제 입력
4
예제 출력
5
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | #include <iostream>using namespace std;long long N;long long X = 1000000007;struct A { long long a; long long b; long long c; long long d; A operator * (A k) { return { (a* k.a + b * k.c)%X , (a* k.b + b * k.d)%X , (c* k.a + d * k.c)%X, (c* k.b + d * k.d)%X }; }};A ArrayN(long long n) { //1 1 x 1 1 x ... n번 //1 0 1 0 if (n == 1) { return{ 1,1,1,0 }; } else if(n == 2) { return{ 2,1,1,1 }; } if ((n & 1) == 1) { // 홀수 return ArrayN(n / 2) * ArrayN(n / 2 + 1); } else { A temp = ArrayN(n / 2); return temp * temp; }} int main() { cin >> N; A a = ArrayN(N); cout << (a.b + a.d) % X << endl; return 0;} |