글 읽기 - [행렬 제곱] 반례 또는 오류 지적 부탁드립니다.

rkdwldnjs9128 2년 전 0

matrix_square()는 행렬곱 연산을 진행하는 부분입니다.

main()함수는 순서대로

1. 문제의 조건에 맞는 입력값 입력

2. b를 이진수로 만드는 과정입니다.(차후 역순으로 읽어옵니다.)

3. 위에서 구한 이진수에 따라 해당 계산을 진행합니다.

일단, 최초의 경우, 연산에 사용할 g를 초기화 합니다.

(0이면 항등원, 1이면 c로 복제)

이후, 읽어온 2진수값에 따라 (제곱)*A연산을 반복합니다.

이후, 계산이 끝난 g를 출력합니다.

이 과정에 따라 진행되고, 문제의 예시 3개는 문제 없이 통과 됩니다.

혹시 띄어쓰기나 줄 바꿈이 출력 조건을 벗어났을까 하여 죄다 if문으로 바꾸고

b의 범위를 상정해서 b도 long long으로 바꾸었고

1000=>0도 걸리지 않으려고

연산마다 >=1000 이면 %1000

하는 계산도 넣어뒀는데

퍼센트가 쭉 올라가다 막히는 것도 아니고, 초장부터 바로 틀려버리니 당황스럽네요.

질문 글들에서 볼 수 있는 반례는

2 1

1000 1000

1000 1000

밖에 안 보여서 질문 글 써봅니다.

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>

using namespace std;


vector< vector<int> > matrix_square(vector< vector <int> > a, vector< vector <int> > b)
{
    int a_size = (a.size());
    int vec_temp = 0;
    vector<vector<int>> temp_maps;

    for (int i = 0; i < a_size; i++)
    {
        temp_maps.push_back(vector<int>());
        for (int j = 0; j < a_size; j++)
        {
            for (int k = 0; k < a_size; k++)
            {
                vec_temp += ((a[i][k]) * (b[k][j]));
                if (vec_temp >= 1000) vec_temp %= 1000;
            }
            temp_maps[i].push_back(vec_temp);
            vec_temp = 0;

        }
    }

    return temp_maps;
}



int main()
{
    int a=0;
    long long b=0;

    vector < vector <int> > c;

   
    int d = 0;
    scanf("%d %d", &a, &b);

    for (int i = 0; i < a; i++)
    {
        c.push_back(vector<int>());
        for (int j = 0; j < a; j++)
        {
            scanf("%d", &d);
            c[i].push_back(d%1000);
        }
    }

    

    vector <int> e;
    while (b>1)
    {
        int f = b % 2;
        b /= 2;

        e.push_back(f);
    }
    e.push_back(b);

    vector<vector<int>> g;

    int vec_temp = 0;
    
   for (int i = 0; i < e.size(); i++)
    {
       if (i == 0)
       {
           switch (e[e.size()-1])
           {

           case 0:
               for (int i=0;i<a;i++)
               {
                   g.push_back(vector<int>());
                   for (int j = 0; j < a; j++)
                   {
                       if (i == j)  g[i].push_back(1);
                       else g[i].push_back(0);
                   }
              }

               break;
           case 1:
               for (int i = 0; i < a; i++)
               {
                   g.push_back(vector<int>());
                   for (int j = 0; j < a; j++)
                   {
                       g[i].push_back(c[i][j]);
                   }
               }
               break;

           default:
               printf("\n이진수 벡터 에러\n");
               break;
           }
       }
       else
       {


           switch (e[e.size() - i - 1])
           {

           case 0:
               g = matrix_square(g, g);

               break;
           case 1:
               g = matrix_square(matrix_square(g, g), c);
               break;

           default:
               printf("\n이진수 벡터 에러\n");
               break;
           }
       }

    }


   for (int i = 0; i < a; i++)
   {
       for (int j = 0; j < a; j++)
       {
           printf("%d", g[i][j]);
           if (j != a - 1) printf(" ");
       }
       if (i != a - 1) printf("\n");
   }
   

    return 0;
}

yeop77 2년 전 1

반례는 없구요

자료형이 long long이면 형식지정자는 %d가 아니라 %lld

rkdwldnjs9128 2년 전 0

세상에... 그런 기초적인 부분에서 실수했었네요 ㅋㅋㅋ

최초에 int로 했다가, 조건 때문에 long long으로 바꾸고

scanf를 안 고쳤었네요

정말 감사합니다 ㅠㅠ

댓글을 작성하려면 로그인해야 합니다.