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

 

https://www.acmicpc.net/problem/10830

10830번: 행렬 제곱

 

주어진 행렬 A에 대하여 입력 B만큼 제곱한 행렬을 출력하는 문제이다.

B는 100,000,000,000 이하의 값을 갖는다. 즉, A를 B번 제곱하는 방식으로는 해결할 수 없다.

분할정복 을 통해 문제를 해결할 수 있다.

A의 거듭제곱은 다음과 같이 나타낼 수 있다.

 

 

 

---

분할정복을 통해 100,000,000,000번 제곱한 값을 찾는다면,

약 36~7번의 연산으로 찾을 수 있다.

최종적으로 시간복잡도는 다음과 같다.

O(logB * N^3)

---

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#define MAX_N 5
#define lli long long int
using namespace std;
using vvi = vector<vector<int> >;
int n;
lli bb;
vvi A(MAX_N, vector<int>(MAX_N, 0));
vvi squaredA;

vvi matMultiply(vvi a, vvi b) {
  vvi res(MAX_N,vector <int>(MAX_N,0));
  int sum;
  for (int r = 0; r < n; r++) {
        for (int c = 0; c < n; c++) {
            sum = 0;
            for (int k = 0; k < n; k++) {
                sum += ((a[r][k] % 1000) * (b[k][c] % 1000)) %1000;
            }
            res[r][c] = sum % 1000;
        }
    }

  return res;
}

vvi solution(lli now) {
  if (now == 1) return A;
  if (now == 2) return squaredA;

  vvi devidedA = solution(now/2);
  vvi squaredDevidedA = matMultiply(devidedA, devidedA);

  if (now % 2) return matMultiply(squaredDevidedA, A);
  else return squaredDevidedA;
}

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> bb;
  for (int i=0; i<n; i++) {
    for(int j=0; j<n; j++) {
      cin >> A[i][j];
    }
  }
  squaredA = matMultiply(A, A);
  vvi res = solution(bb);

  for (int i=0; i<n; i++) {
    for (int j=0; j<n; j++) {
      cout << res[i][j] % 1000 << " ";
    }
    cout << "\n";
  }
}