(10830) 행렬 제곱

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

단계별로 풀어보기

24단계(분할 정복) 7번째

 

 

 

숫자 하나가 행렬로 바뀌었다는 점만 빼면 거듭제곱 함수를 그대로 쓰면 된다.

거듭제곱을 하기 전 res의 기저값이었던 1이 행렬에서는 단위 행렬이다.

또한 행렬의 곱셈을 쉽고 빠르게 하기 위해 연산자 오버로딩으로 행렬의 곱셈을 정의하였다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;
#define p 1000
typedef vector<vector<long>> matrix;

matrix operator*(const matrix &a, const matrix &b){
  matrix res(a.size(), vector<long> (b[0].size()));

  for(int i=0;i<res.size();i++){
    for(int j=0;j<res[0].size();j++){
      for(int k=0;k<a[0].size();k++){
        res[i][j]+= a[i][k]*b[k][j];
      }
      res[i][j]%= p;
    }
  }

  return res;
}

matrix power(matrix &base, long expo){
  matrix res(base.size(), vector<long> (base.size()));
  
  for(int i=0;i<base.size();i++)  res[i][i]= 1;
  
  while(expo){
    if(expo&1)  res= res*base;
    expo/= 2;
    base= base*base;
  }
  
  return res;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  long n, b;
  
  cin >> n >> b;
  
  vector a(n, vector<long> (n));
  
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      cin >> a[i][j];
    }
  }
  
  a= power(a, b);
  
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      cout << a[i][j] << " ";
    }
    cout << "\n";
  }
  
  return 0;
}