[알고리즘] 행렬 제곱

구현 방식

• 행렬 mat 의 4 제곱은 mat^4 = mat^2 * mat^2 = mat * mat * mat * mat 와 같다.
• 행렬 mat 의 5 제곱은 mat^4 = mat^2 * mat^2 * mat = mat * mat * mat * mat * mat 와 같다.
• 즉 짝수 제곱은 mat^N = mat^(N/2) * mat^(N/2) 이며, 홀수 제곱은 mat^N = mat^(N/2) * mat^(N/2) * mat 로 나타낼 수 있다.
• 분할 정복 및 이전에 방문한 내용 기록을 통해서 풀도록한다.
• 행렬 곱을 편하게 하기위해 * operator 연산을 할 수 있는 Matrix 클래스를 만들었다.

코드

• 최종 코드는 아래와 같다.

const int MATMAXSIZE = 5;
const int MOD = 1000;

map<long long, Matrix> dict;

class Matrix
{

public:
	Matrix() { }
	Matrix(int N) : Size(N) { }

public:
	Matrix operator*(const Matrix& m)
	{
		Matrix result(Size);
		for (int i = 0; i < Size; i++)
		{
			for (int j = 0; j < Size; j++)
			{
				for (int k = 0; k < Size; k++)
					result.mat[i][j] += this->mat[i][k]  * m.mat[k][j];
				result.mat[i][j] %= 1000;
			}
		}

		return result;
	}

	static void print(Matrix m)
	{
		for (int i = 0; i < m.Size; i++)
		{
			for (int j = 0; j < m.Size; j++)
			{
				cout << m.mat[i][j] << " ";
			}
			cout << "\n";
		}
	}

public:
	int Size;
	int mat[MATMAXSIZE][MATMAXSIZE] = {};
};


int  main()
{
	int N;
	long long B;
	cin >> N >> B;

	Matrix Mat(N);

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
		{
			cin >> Mat.mat[i][j];
			Mat.mat[i][j] %= 1000;
		}

	solution(Mat,  B);
	

}


void solution(Matrix& Mat,long long B)
{
	dict[1] = Mat;
	Matrix result = calcExponent(B);
	Matrix::print(result);
	
}

Matrix calcExponent(long long expo)
{
	if (dict.find(expo) != dict.end())
		return dict[expo];
	// 홀 수
	if (expo % 2 == 1)
	{
		dict[expo] = calcExponent(expo / 2) * calcExponent(expo / 2)* calcExponent(1);
		return dict[expo];
	}
	// 짝 수
	else
	{
		dict[expo] = calcExponent(expo / 2) * calcExponent(expo / 2);
		return dict[expo];
	}
}