백준 10830번 행렬 제곱 C++

출처 : https://www.acmicpc.net/problem/10830

 

a^b에서 b가 홀수라면 b를 1 빼주고 결과(처음에는 단위행렬)에 a를 곱해주고

b가 짝수라면 a^b = (a^2)^(b/2) 이기 때문에 a를 제곱해주고 b를 2로 나눠주었다.

 

2^7를 예로 들자면

우선 처음에 결과는 1로 시작한다. (res = 1)

2^7 에서 7이 홀수이기 때문에 2^6 으로 바꾸고 res에 2를 곱한다 (res = 2)

2^6 에서 6이 짝수이기 때문에 4^3으로 바꿔준다.

4^3에서 3이 홀수이기 때문에 4^2로 바꿔주고 res에 4를 곱한다(res = 8)

4^2에서 2가 짝수이기 때문에 16^1로 바꿔준다.

16^1에서 1이 홀수이기 때문에 16^0으로 바꿔주고 res에 16을 곱한다(res = 128)

b가 0이 됐기 때문에 그만 계산한다.

 

2^7 = res = 128이다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

int n;
int64 b;

struct Matrix {
	Matrix(int size) :size(size) 
	{
		v = vector<vector<int64>>(size, vector<int64>(size, 0));
		for (int i = 0; i < size; i++)
			v[i][i] = 1;
	}
	Matrix(int size, int val) :size(size)
	{
		v = vector<vector<int64>>(size, vector<int64>(size, val));
	}
	int size;
	vector<vector<int64>> v;
};

Matrix operator*(const Matrix& lhs, const Matrix& rhs) {
	int size = lhs.size;
	Matrix ret = Matrix(size, 0);
	for (int i = 0; i < size; i++) {
		for (int j = 0; j < size; j++) {
			for (int k = 0; k < size; k++) {
				ret.v[i][j] += lhs.v[i][k] * rhs.v[k][j];
			}
			ret.v[i][j] %= 1000;
		}
	}
	return ret;
}

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

	cin >> n >> b;
	Matrix ans = Matrix(n);
	Matrix mat = Matrix(n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int val;
			cin >> val;
			mat.v[i][j] = val;
		}
	}
	while (b) {
		if (b % 2 == 0) {
			mat = mat * mat;
			b /= 2;
		}
		else {
			ans = ans * mat;
			b--;
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << ans.v[i][j] << " ";
		}
		cout << "\n";
	}
};