문제 ID : MATEXP 질문 드립니다.!!

  • sangsang
    sangsang

    https://algospot.com/judge/problem/read/MATEXP

    #include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <cstring>
    using namespace std;
    
    int MOD = 10007;
    
    int how_many[30];
    int N;
    int matrix[30][102][102];
    int p;
    int answer_matrix[102][102];
    int multi(int po);
    void solve(int po);
    void print_matrix(int aaa[102][102]);
    int main(){
        freopen("input.txt","r",stdin);
    
        int TC; cin>>TC;
    
        for(int test_case = 0 ; test_case < TC ; test_case++){
            cin>>N>>p;
            memset(matrix, 0, sizeof(matrix));
            memset(how_many, 0, sizeof(how_many));
            memset(answer_matrix, 0, sizeof(answer_matrix));
            for(int i = 1 ; i <= N ; i++){
                for(int j = 1; j <= N ; j++){
                    cin>>matrix[0][i][j];
                }
            }
    
    
            int aaa = multi(1);
            how_many[0] = aaa;
            int first;
            for(int i = 0 ; i < 30; i++){
                if(how_many[i]){
                    first = i;
                    break;
                }
            }
    
            for(int i = 1 ; i <= N; i++){
                for(int j = 1 ; j <= N; j++){
                    answer_matrix[i][j] = matrix[first][i][j];
                }
            }
    
            solve(first + 1);
    
            print_matrix(answer_matrix);
    
        }
        return 0;
    }
    
    int multi(int po){
        if(pow(2,po) > p) return -1;
        for(int i = 1 ; i <= N; i++){
            for(int j = 1; j <= N; j++){
                for(int k = 1; k <= N; k++){
                    matrix[po][i][j] += (matrix[po-1][i][k]*matrix[po-1][k][j]);
                }
                matrix[po][i][j] %= MOD;
            }
        }
    
        int aaa = multi(po + 1);
    
        if(aaa == -1){
            how_many[po] = p / pow(2, po);
            return (p % (int)pow(2,po));
        }
        else{
            how_many[po] = aaa / pow(2,po);
            return (aaa % (int)pow(2, po));
        }
    
    }
    
    void solve(int po){
        if(pow(2,po) > p) return;
    
    
        if(how_many[po]){
            int prev_matrix[102][102];
            for(int i = 1; i <= N; i++){
                for(int j = 1; j <= N; j++){
                    prev_matrix[i][j] = answer_matrix[i][j];
                }
            }
            int a;
            for(int i = 1; i <= N; i++){
                for(int j = 1; j <= N; j++){
                    a = 0;
                    for(int k = 1; k <= N; k++){
                        a += (prev_matrix[i][k] * matrix[po][k][j]);
                    }
                    answer_matrix[i][j] = a %  MOD;
                }
            }
        }
        solve(po + 1);
    
    }
    
    void print_matrix(int aaa[102][102]){
        for(int i = 1; i <= N ; i++){
            for(int j = 1; j <= N; j++){
                cout<<aaa[i][j]<<" ";
            }
            cout<<endl;
        }
    }
    

    저의 코드입니다.

    저의 알고리즘은

    p를 2진수로 나타내고,

    필요한 숫자들을 저장했다가,

    예를들어 11이면 8 + 2 + 1을 저장하는 것입니다.

    그리고 동시에

    입력 행렬의 2^n 승, 즉 1승 2승 4승 8승.. 등등을 저장을 matrix에 해놓습니다.

    그런 다음 내가 필요한 것을

    answer_matrix에 가져와서 곱하는 형태입니다.

    저의 알고리즘에서 틀린 부분이 어디에 있는지. ㅠㅠ 고수님들 답변 부탁드립니다.


    8년 전
1개의 댓글이 있습니다.
  • 일루
    일루

    100007 * 10007 * N >= 2^31? 확인해보세요...

    ps) pow는 실수형 리턴이라 권장하지 않습니다...


    8년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.