[백준][C++] 10830: 행렬 제곱

문제

풀이

• N이 상당히 크기때문에 분할 정복으로 푼다.
  • N이 짝수 일 경우 N / 2와 N / 2
  • N이 홀수 일 경우 N - 1과 N
• 행렬을 곱하면서 수가 점점 커지기 때문에 곱하면서 MOD연산이 필요하다.

코드

#include <iostream>
#include <vector>
#include <map>

#define MOD 1000

using namespace std;

int N;
long long B;
map<long long, vector<vector<long long>>> cache;
vector<vector<long long>> matrix;

vector<vector<long long>> mulMatrix(vector<vector<long long>> m1, vector<vector<long long>> m2)
{
    vector<vector<long long>> outMatrix;
    outMatrix.resize(N);
    for (int i = 0; i < N; ++i)
    {
        outMatrix[i].resize(N);
    }

    // m1과 m2 행렬의 곱
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            for (int k = 0; k < N; ++k)
            {
                outMatrix[i][j] += (m1[i][k] * m2[k][j]);
            }
            outMatrix[i][j] %= MOD;
        }
    }

    return outMatrix;
}

vector<vector<long long>> solution(long long n)
{
    if (n == 1)
    {
        return matrix;
    }

    if (!cache[n].empty())
    {
        return cache[n];
    }

    // n이 짝수, 홀수일 경우 나눠서 분할 정복
    if (n % 2 == 0)
    {
        cache[n] = mulMatrix(solution(n / 2), solution(n / 2));
        return cache[n];
    }
    else
    {
        cache[n] = mulMatrix(solution(n - 1), matrix);
        return cache[n];
    }
}

int main()
{
    cin >> N >> B;

    matrix.resize(N);
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            int temp;
            cin >> temp;
            matrix[i].push_back(temp);
        }
    }

    cache[1] = matrix;

    vector<vector<long long>> answer = solution(B);

    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            cout << answer[i][j] % MOD << " ";
        }
        cout << endl;
    }

    return 0;
}