10830

[백준/BOJ 알고리즘] 10830 행렬 제곱 C++

https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 주어진 행렬 A에 대하여 입력 B만큼 제곱한 행렬을 출력하는 문제이다. B는 100,000,000,000 이하의 값을 갖는다. 즉, A를 B번 제곱하는 방식으로는 해결할 수 없다. 분할정복 을 통해 문제를 해결할 수 있다. A의 거듭제곱은 다음과 같이 나타낼 수 있다. 분할정복을 통해 100,000,000,000번 제곱한 값을 찾는다면, 약 36~7번의 연산으로 찾을 수 있다. 최종적으로 시간복잡도는 다음과 같..