수 제한이 엄청 커서 피보나치 수 구할 때 행렬곱셈 등 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)은 안되는 거였다면 수정해주시면 감사하겠습니다.
수정했습니다.
댓글을 작성하려면 로그인해야 합니다.
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)은 안되는 거였다면 수정해주시면 감사하겠습니다.