Development Artist

도입 백준 단계별 풀기에서 분할정복 일곱 번째 문제이다. 풀이 1.1. 행렬의 거듭제곱을 어떤식으로 할 것인가! 정사각형 행렬 A를 13번 거듭제곱을 한다고 가정해보자. A의 제곱부터 차례차례 A를 곱하는 방법이 있다. 하지만, 이렇게 하지 않는다. $A^{13}$이 $(A^6)^2*A$ 으로 표시할 수 있고, 여기서 $A^6$을 알고 있다면? 제곱연산을 2번만 하면 된다. 1.2. 지수가 홀수인가, 짝수인가. 홀수라면 $(A^k)*A$ 일 것이고, 짝수라면 $(A^k)^2$ 으로 표현할 수 있다. 1.3. 13을 2진법으로 표현해보자. $1101_2$ 이다. MSB로 계산을 한다. (LSB아님) 1일 때는 홀수로 계산하고 0일때는 짝수로 계산. 1 - $(A^0)^2*A$ = $A$ 1 - $(A^1)..