Fast Matrix Exponentiation

문제: MATEXP / 분할정복

한 번에 한 번씩 계산해서는 시간내에 해결할 수 없다. 그렇다면? 반 씩 나누어서 계산하면 빠르게 해결할 수 있다.

1*1 행렬 계산을 해서 승수 2에 대한 값을 만들고, 다시 2*2를 해서 승수 4에 대한 값을 만들고.. 이런 식으로 하면 logN번만 계산하면 된다. 

100 by 100 행렬 계산에 그리 큰 시간이 소요되지 않으므로, 행렬 계산은 단순하게 3중 loop로 처리했다. 

총 복잡도는 

코드: https://github.com/xgate/algospot/blob/master/DIV/MATEXP.cpp