on2130   3년 전

모듈러 연산을 염두하여

행렬제곱을 연산했는데

단순히 함수만 불러오는 방식이 너무 비효율적인거같은데

메모이제이션을 하자니 저장할 배열크기가 너무 큰거같고

너무 무작정 코딩한건가요?

Green55   3년 전

B가 너무 크기 때문에, 곱셈을 B번 직접 해줘서는 시간 내에 불가능합니다.

https://www.acmicpc.net/proble... 에 나와있는 방법을 사용하면 logB번의 행렬 곱셈만으로도 답을 구할 수 있습니다.

pch6828   3년 전

AN의 연산을 단순히 A*A*A*A....의 형식으로 구하게 되면 이 문제는 시간초과를 받게 됩니다.

여기서는 AN = (AN/2)2or (AN/2)2*A 라는 규칙에 따라서 재귀적으로 구하셔야 합니다.

이런식으로 구하게 될 경우 시간복잡도가 O(logN)이 되기 때문에 시간 초과를 피할 수 있습니다.

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