[BaekJoon][10830] 행렬 제곱

BAEKJOON ONLINE JUDGE

10830 행렬 제곱

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

행렬 곱을 반복

반복을 분할 정복 또는 이진수 응용법으로 시간을 단축할 수 있다.

#include <cstdio>
#include <vector>
using namespace std;
 
int n;
long long int m;
vector<vector<int>> in;
 
void input()
{
    int num;
 
    scanf("%d %lld", &n, &m);
 
    for (int i = 0; i < n; i++) {
        vector<int> v;
        for (int j = 0; j < n; j++) {
            scanf("%d", &num);
            v.push_back(num);
        }
        in.push_back(v);
    }
}
 
vector<vector<int>> multipleMatrix(vector<vector<int>> &first, vector<vector<int>> &second)
{
    vector<vector<int>> ans(n, vector<int>(n));
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                ans[i][j] += first[i][k] * second[k][j];
            }
            ans[i][j] %= 1000;
        }
    }
    return ans;
}
 
vector<vector<int>> powMatrix(vector<vector<int>> &matrix, long long int b)
{
    vector<vector<int>> ans(n, vector<int>(n));
    vector<vector<int>> arr = matrix;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j)    ans[i][j] = 1;
            else            ans[i][j] = 0;
        }
    }
 
    while (b > 0) {
        if (b % 2)         
            ans = multipleMatrix(ans, arr);
        arr = multipleMatrix(arr, arr);
        b /= 2;
    }
    return ans;
}
 
void print(vector<vector<int>> v)
{
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%d ", v[i][j]);
        }
        printf("\n");
    }
}
 
int main()
{
    input();
 
    print(powMatrix(in, m));
 
    return 0;
}