[백준 10830번] 행렬 제곱 (C++)

문제링크 : https://www.acmicpc.net/problem/10830

10830번: 행렬 제곱

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;
typedef vector<vector<ll>> matrix;

ll N, B;

matrix multiply(matrix &a, matrix &b)
{
    matrix temp(N, vector<ll>(N));
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            for(int k=0; k<N; k++)
            {
                temp[i][j] += (a[i][k] * b[k][j]);
            }
            temp[i][j] %= 1000;
        }
    }

    return temp;
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N >> B;
    matrix arr(N, vector<ll>(N));
    matrix result(N, vector<ll>(N));

    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            cin >> arr[i][j];
        }
        result[i][i] = 1; // 단위행렬로 초기화
    }

    while(B)
    {
        if(B%2) result = multiply(result, arr); //홀수 (한번 더 곱해줌)
        arr = multiply(arr, arr); //짝수
        B/=2;
    }

    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            cout << result[i][j] << " ";
        }
        cout <<"\n";
    }

    return 0;
}

[백준 11444번] 피보나치 수 6 문제를 푸는 방법과 거의 동일하게 푸는 문제이다.

피보나치 수 6 문제에서 행렬 제곱을 계산하는 방법 (거듭 제곱) 이 사실상 이 문제를 푸는 방법이다.

 

그래서 크게 설명한 것은 없고 간단하게 다시 쓰면

B = 5 가정

5 = 4*1
  = (2*2)*1
  = (1*1)*(1*1)*1

위와 같으므로, 짝수 일때는 같은 값을 제곱해주고 홀수 일때는 해당 값을 한번만 더 곱해주면 된다.

 

여기서 또 실수를 했었는데, B의 범위가 매우 크므로 long long을 선언해줘야 했다.

여기서도 N이랑 같이 int로 선언했다가 여러번 틀렸다.