코딩스토리

https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 행렬 제곱 DP를 공부하기 위해 먼저 이 문제를 풀어보았다. 주어진 조건 중 "1 ≤ B ≤ 100,000,000,000"을 보고 저게 내 통장 잔고였음 좋겠다... 뻘 생각 한번 해주고 시간 복잡도는 O(logN)으로 구해야겠다 싶었다. 내가 문제를 보고 생각했던 logN 풀이는 반드시 (A^2)*(A^2) = A^4를 만족해야 했다. 나는 행렬을 고등학교때 배우고 온 세대가 아니기 때문에(나름 신생아^^) ..