[BOJ 13328 // C++] Message Passing

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 13328번 문제인 Message Passing이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/13328

13328번: Message Passing

이 문제에서 맨 처음 연락을 돌리는 Kim씨를 제외하면 모든 사람들은 1분 간격으로 d번 연락을 한다. 즉, 어떤 x분 시점에서 연락을 받는 사람들은 x-1, x-2, x-3, ... , x-d 분 전에 연락을 받은 사람이 돌린 통화라고 해석할 수 있다. 이 점화관계를 행렬로 나타내서 binary exponentiation을 이용하면 문제를 해결할 수 있다.

 

다음은 이해를 돕기 위한 단순한 예시이다.

 

[ 1 1 1 1 1 ] [ a_7 ]    [ a_8 ]

[ 1 0 0 0 0 ] [ a_6 ]    [ a_7 ]

[ 0 1 0 0 0 ] [ a_5 ] = [ a_6 ]

[ 0 0 1 0 0 ] [ a_4 ]    [ a_5 ]

[ 0 0 0 1 0 ] [ a_3 ]    [ a_4 ]

 

아래는 제출한 소스코드이다.

#include <iostream>
using std::cin;
using std::cout;

long long mat[51][50];
long long mtt[50][50];
long long vec[50];
long long tmp[50];

int main()
{
    vec[0] = 1; // vec = { a_0, 0, 0, ..., 0 }

    int d, t;
    cin >> d >> t;
    for (int i = 0;i < d;i++) { // 문제에 주어진 점화관계를 d by d 행렬로 나타내기
        mat[0][i] = 1;
        mat[i + 1][i] = 1;
    }
    while (t > 0) { // 위에서 만든 행렬의 t제곱을 vec에 곱하면 { a_t, a_(t-1), ... , a_(t-d+1) } 가 된다.
        if (t & 1) { // binary exponentiation
            for (int i = 0;i < d;i++) {
                for (int j = 0;j < d;j++) {
                    tmp[i] += mat[i][j] * vec[j];
                }
            }
            for (int j = 0;j < d;j++) {
                vec[j] = tmp[j]%31991;
                tmp[j] = 0;
            }
        }
        for (int i = 0; i < d; i++) {
            for (int j = 0;j < d;j++) {
                for (int k = 0;k < d;k++) {
                    mtt[i][j] += mat[i][k] * mat[k][j];
                }
            }
        }
        for (int i = 0; i < d; i++) {
            for (int j = 0;j < d;j++) {
                mat[i][j] = mtt[i][j]%31991;
                mtt[i][j] = 0;
            }
        }
        t >>= 1;
    }
    cout << vec[0];

    return 0;
}