[BAEKJOON] 10830번 : 행렬 제곱

[ ALGORITHM ]/[ 백 준 ]

[BAEKJOON] 10830번 : 행렬 제곱

HiStar__ 2020. 8. 8. 11:13

문 제

소 스 코 드

#include <iostream>

constexpr int MOD{ 1'000 };

typedef long long INT;

class MATRIX__ {
private:
	int * arr;
	int size;

public:
	MATRIX__() {}
	~MATRIX__() { delete[] arr; }

public:
	void Init(const int& s, const int& index) {
		size = s;
		
		arr = new int[size];

		for (int i = 0; i < size; ++i) 
			if(index == i) arr[i] = 1;
			else arr[i] = 0;
			
	}

	void Reset() {
		for (int i = 0; i < size; ++i) arr[i] = 0;
	}

	void Input() {
		for (int i = 0; i < size; ++i) {
			std::cin >> arr[i];
		}
	}

	void Display() {
		for (int i = 0; i < size; ++i) std::cout << arr[i] << " ";
	}

	int operator[] (const int& index) const {
		return arr[index];
	}
	int& operator [](int index) {
		return arr[index];
	}

	MATRIX__& operator =(const MATRIX__& other) {
		if (this == &other) return *this;
		for (int i = 0; i < size; ++i) arr[i] = other.arr[i];
		return *this;
	}


};

class MATRIX {
private:
	MATRIX__* m_arr;
	int m_size;

public:
	MATRIX() = delete;
	MATRIX(const int& size) : m_size{ size }, m_arr{ new MATRIX__[size] }{
		for (int i = 0; i < m_size; ++i) m_arr[i].Init(m_size, i);
	}
	~MATRIX() { delete[] m_arr; }

	MATRIX& operator = (const MATRIX& other) {
		if (this == &other) return *this;
		for (int i = 0; i < m_size; ++i) m_arr[i] = other.m_arr[i];
		return *this;
	}


public:
	void Input(){
		for (int i = 0; i < m_size; ++i) m_arr[i].Input();
	}
	void Init() {
		for (int i = 0; i < m_size; ++i) m_arr[i].Reset();
	}
	void Display() {
		for (int i = 0; i < m_size; ++i) {
			m_arr[i].Display();
			std::cout << '\n';
		}
	}

	MATRIX__& operator[](int index) {
		return *(m_arr + index);
	}

	MATRIX__ operator[](const int& index) const{
		return *(m_arr + index);
	}
};



void SquareOfMatrix();
void Square(MATRIX&, MATRIX&, MATRIX&, INT, const int&);
void Multi(MATRIX&, MATRIX&, MATRIX&, const int&);

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	SquareOfMatrix();

	return 0;
}

void SquareOfMatrix() {
	int N;
	INT S;
	std::cin >> N >> S;

	MATRIX A{ N };
	MATRIX B{ N };
	MATRIX C{ N };

	A.Input();

	Square(A, B, C, S, N);

	B.Display();
}




void Square(MATRIX& A, MATRIX& B, MATRIX& C, INT length, const int& n) {
	while (length != 0) {
		
		if (length & 1) {
			C.Init();
			Multi(A, B, C, n);
			B = C;
		}

		C.Init();
		Multi(A, A, C, n);
		A = C;

		length >>= 1;
	}
}


void Multi(MATRIX& A, MATRIX& B, MATRIX& C, const int& 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] += ((A[i][k] * B[k][j])) % MOD;
			}
			C[i][j] %= MOD;
		}
	}
}

풀 이

홀수 일 때 처음에 행렬의 경우 단위 행렬 E여야 한다!

행렬의 제곱 또한

짝수 일 경우,

$$ \left( \begin{bmatrix}a & b \\c & d \end{bmatrix} \right)^ {2\left({n}\right)} $$

홀수 일 경우,

$$\begin{bmatrix}a & b \\c & d \end{bmatrix} * \left( \begin{bmatrix}a & b \\c & d \end{bmatrix} \right)^ {n}$$

출 력 값