코난도일의 자유로이~!

문제 링크 : http://algospot.cafe24.com/zbxe/?mid=aoj&action=problem&no=132




제출한 답안 :


#include <iostream>
#include <stdlib.h>

using namespace std;

class Mat
{
public:

 long long **matrix;
 long long size;

 Mat();
 Mat(long long n);
 Mat(const Mat& mat);
 ~Mat();

 Mat operator*(const Mat& mat);
 void operator=(const Mat& mat);

};

Mat::Mat()
{
}

Mat::Mat(long long n)
{
 size = n;

 matrix = new long long*[n];

 for(long long j = 0; j < n; j++)
 {
  matrix[j] = new long long[n];
 }
}

Mat::Mat(const Mat& mat)
{
 long long i, j;

 size = mat.size;

 matrix = new long long*[size];

 for(i = 0; i < size; i++)
 {
  matrix[i] = new long long[size];
 }

 for(i = 0; i < size; i++)
 {
  for(j = 0; j < size; j++)
  {
   matrix[i][j] = mat.matrix[i][j];
  }
 }
}

Mat::~Mat()
{
  for(long long i = 0; i < size; i++)
  {
   delete [] matrix[i];
  }

  delete [] matrix;
}

Mat Mat::operator*(const Mat& mat)
{
 long long i, j, k;

 Mat c(size);

 for(i = 0; i < size; i++)
 {
  for(j = 0; j < size; j++)
  {
   c.matrix[i][j] = 0;
   
   for(k = 0; k < size; k++)
    c.matrix[i][j] += matrix[i][k] * mat.matrix[k][j];

   c.matrix[i][j] %= 10007;
  }
 }

 return c;

}

void Mat::operator=(const Mat& mat)
{
 long long i, j;

 size = mat.size;

 matrix = new long long*[size];

 for(i = 0; i < size; i++)
 {
  matrix[i] = new long long[size];
 }

 for(i = 0; i < size; i++)
 {
  for(j = 0; j < size; j++)
  {
   matrix[i][j] = mat.matrix[i][j];
  }
 }
}

Mat matrix_pow(Mat a, long long p)
{
 long long i, j;

 if(p == 0)
 {
  Mat E(a.size);

  for(i = 0; i < a.size; i++)
  {
   for(j = 0; j < a.size; j++)
   {
    E.matrix[i][j] = 0;

    if(i == j)
     E.matrix[i][j] = 1;
   }   
  }

  return E;
 }
 else if(p % 2 == 1)
 {
  return a * matrix_pow(a, p - 1);

 }
 else
 {
  Mat b = matrix_pow(a, p / 2);

  return b*b;
 }
}

int main(void)
{
 
 int ncase, n, i = 0, j, k;
 long long p;

 Mat* M;
 Mat* result;

 cin >> ncase;

 while(i < ncase)
 {
  cin >> n;
  cin >> p;

  M = new Mat(n);
  result = new Mat(n);

  for(j = 0; j < n; j++)
  {
   for(k = 0; k < n; k++)
    cin >> M->matrix[j][k];
  }

  *result = matrix_pow(*M, p);

  for(j = 0; j < n; j++)
  {
   for(k = 0; k < n; k++)
    cout << result->matrix[j][k] % 10007 << " ";

   cout << "\n";
  }
 
 
  delete M;
  delete result;

  i++;
 }

 return 0;
}


변수 타입 long long으로 지정하는걸 몰라서 한참 고생했다.ㅡㅜ