문제

문제 링크

어떻게 접근할 것인가

  • mat1은 항등행렬로 저장하고 mat2에는 값을 넣어서 저장한다.
  • B를 이진수로 변환해서 이진수를 쭉 돌면서 연산한다.
  • 1이면 mat1 = (mat1 * mat1) * mat2 이고,
  • 0이면 mat1 = (mat1 * mat1) 해준다.

주의할 점

  • 매 연산마다 꼭 mod를 해줘야한다!

코드

#include <cstdio>
#include <vector>

using namespace std;

vector<vector<long long> >matrix_multi(vector<vector<long long> > a, vector<vector<long long> > b, long long n){
    vector<vector<long long> > c(n, vector<long long>(n));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            for(int k = 0; k < n; k++){
                c[i][j] += (long long)a[i][k] * b[k][j];
                c[i][j] %= 1000;
            }
        }
    }
    return c;
}

vector<int> to_binary(long long num){
    vector<int> v;
    while(num != 0){
        v.push_back(num%2);
        num/=2;
    }
    return v;
}

int main(){
    long long n, b, input;
    scanf("%lld %lld", &n, &b);
    vector<vector<long long> > mat1(n, vector<long long>(n));
    vector<vector<long long> > mat2(n, vector<long long>(n));


    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            scanf("%lld", &input);
            mat2[i][j] = input;
        }
    }
    for(int i = 0; i < n; i++)mat1[i][i] = 1;
    
    vector<int> v = to_binary(b);
    for(int i = v.size() - 1; i >= 0; i--){
        if(v[i] == 1) {
            mat1 = matrix_multi(mat1, mat1, n);
            mat1 = matrix_multi(mat1, mat2, n);
        }
        else mat1 = matrix_multi(mat1, mat1, n);

    }
    

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++)printf("%lld ", mat1[i][j]);
        printf("\n");
    }
    
}

느낀점

  • 진짜… 이 문제 얼마나 오래 잡고 있던 건지 모르겠다. 수학 공식을 보긴했어도 제대로 보지 않는 바람에 계속 답을 내지 못하고 있었다.
  • 다음에는 수식을 찾아보더라도 제대로 이해하고 사용해야겠다!