[BOJ] 10830 - 행렬 제곱

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

BOJ - 행렬 제곱

문제 유형: 행렬, 재귀, 분할 정복

문제 난이도: Gold IV

시간 제한: 1초

메모리 제한: 256MB

 

문제

크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.

 

입력

첫째 줄에 행렬의 크기 N과 B가 주어진다. (2 ≤ N ≤  5, 1 ≤ B ≤ 100,000,000,000)

둘째 줄부터 N개의 줄에 행렬의 각 원소가 주어진다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0이다.

 

출력

첫째 줄부터 N개의 줄에 걸쳐 행렬 A를 B제곱한 결과를 출력한다.

 

풀이

행렬 A가 있다고 해보자.

 

행렬 A의 거듭제곱은 짝수인 경우,

A^n = A^{n-2} * A^{n-2}

홀수인 경우,

A^n = A^{n-1} * A

라는 성질이 있다.

행렬의 크기가 5 x 5 이내이므로, 공간적 여유는 충분하다.

중요한 건 b에 대해 로그로 증가하도록 처리하는 것이다.

 

C =A x B의 행렬곱은..

곱해진 행렬 c_ij = [A_i행]과 [B_j열]의 값들의 pointwise 곱셈값의 합이다.

 

재귀 호출로 b를 호출해서, 그 결과를 출력해주면 된다.

b가 상당히 크므로, 수 범위를 고려하도록 하고, %1000도 잊지 말자.

 

코드

C++

#include <bits/stdc++.h>
#define ll long long

using namespace std;

ll n, b;
vector<vector<int>> mat;

int calc(int i, int j, vector<vector<int>> &m1, vector<vector<int>> &m2) {
  // i row x j col
  int res = 0;
  for (int k = 0; k < n; ++k) {
    res += m1[i][k] * m2[k][j];
    res %= 1000;
  }
  return res;
}

vector<vector<int>> solve(ll x) {
  if (x == 1) {
    return mat;
  }

  vector<vector<int>> res(n, vector<int>(n));
  if (x % 2 == 0) {
    auto m = solve(x / 2);
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        res[i][j] = calc(i, j, m, m);
      }
    }
    return res;
  } else {
    auto m = solve(x - 1);
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        res[i][j] = calc(i, j, m, mat);
      }
    }
    return res;
  }
}

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  cin >> n >> b;
  mat.resize(n, vector<int>(n));
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      cin >> mat[i][j];
      mat[i][j] %= 1000;
    }
  }

  auto ans = solve(b);
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      cout << ans[i][j] << " ";
    }
    cout << "\n";
  }

  return 0;
}