10830번 행렬 제곱

https://www.acmicpc.net/problem/10830 필요한 로직 : 분할 정복 [논리] A^15 = A*A*A*(...)*A 으로 15번의 matrix multification이 필요하다. 지수승에 해당하는 B의 상한이 1000억이 되기 때문에, 제한 시간내 O(N^3)의 곱셈 과정을 B번 반복할 수 없다. 이 문제를 해결하기 위해서는 분할 정복을 연상하며 지수승을 낮출 수 있다. 예를 들어 A^15은 A^(8+4+2+1)으로 표현될 수 있으며, 최종적으론 A^(11110(2)) 으로 지수를 이진수로 변환해 풀이해볼 수 있다. 이렇게 되면, A를 2번 곱한 tmp arr가 0/1/2/3번 지수승한 결과를 반환하면 되며, 이 값들을 단위 행렬에 차례로 곱해나가는 식으로 4번의 연산을 추가하면 된다. 즉 15번의 과..........

원문링크 : 10830번 행렬 제곱