백준 10830번 행렬 제곱 문제풀이(C++)

백준 10830번 행렬 제곱

아이디어

n이 5라 했을 때
n&1 == 1 -> ans = a, a = a^2 // n/=2 -> 2
n&1 != 1 -> a = a^2 // n/=2 -> 1
n&1 == 1 -> ans = ans a -> a a^4 = a^5, a = a^8

n이 홀수 일때만 ans에 곱해주면 해당 제곱수를 구할 수 있다.

문제해결

#include<bits/stdc++.h>
using namespace std;
#define MOD 1000
typedef long long ll;
typedef vector<vector<ll>> matrix;
ll n, m;
matrix operator *(matrix& a, matrix& b) {
	matrix temp(n, vector<ll>(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < n; k++) {
				temp[i][j] += a[i][k] * b[k][j];
			}
			temp[i][j] %= MOD;
		}
	}
	return temp;
}
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m;
	matrix a(n, vector<ll>(n)), ans(n, vector<ll>(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> a[i][j];
		}
        // 단위 행렬 사용
		ans[i][i] = 1;
	}
	while (m) {
		if (m & 1)ans = ans * a;
		a = a * a;
		m /= 2;
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << ans[i][j] << ' ';
		}
		cout << '\n';
	}
	return 0;
}