kdh9949   8년 전

수 제한이 엄청 커서 피보나치 수 구할 때 행렬곱셈 등 O(logN) 방법을 사용하라는 의도가 있는 거 같은데...

O(N)으로 피보나치 수 구해도 통과가 되는 거 같습니다. (바로 아래 코드처럼)

a = 0, b = 1;
    for(long long i = 2; i <= x; i++){
        c = a + b;
        a = b;
        b = c;
        a %= mod;
        b %= mod;
    }

https://www.acmicpc.net/source/1186640 참고해 주세요.

만약 원래 의도한 것이 O(logN) 방법만 통과되고 O(N)은 안되는 거였다면 수정해주시면 감사하겠습니다.

baekjoon   8년 전

수정했습니다.

댓글을 작성하려면 로그인해야 합니다.