백준 10830 행렬 제곱 (c++) : 피너클

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

10830번: 행렬 제곱

수학문제다.

cin >> n >> b;
for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
		cin >> p[i][j];
	}
	ans[i][i] = 1;
}

값을 입력받는다. p에는 처음 받는 행렬이 주어지고 ans에는 답으로 출력될 행렬을 저장한다.

while (b > 0) {
	if (b % 2 == 1) {
		solve(ans, p);
	}
	b /= 2;
	solve(p, p);
}

그후 b가 0보다 큰동안 반복문을 돌린다.

만약 b가 홀수라면 solve(ans, p)를 돌리고 아니면 solve(p, p)를 돌린뒤 b를 2로 나눈다.

위의 형태는 거듭제곱을 분할정복으로 푸는 형태중 하나다.

void solve(long long a[5][5], long long b[5][5]) {
	long long sam[5][5];

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			sam[i][j] = 0;
			for (int k = 0; k < n; k++) {
				sam[i][j] += a[i][k] * b[k][j];
			}
			sam[i][j] %= 1000;
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			a[i][j] = sam[i][j];
		}
	}
}

solve는 간단하다. 행렬 2개를 전달받아 서로를 곱한뒤  전달받은 행렬중 하나에 그 값을 저장하면 된다.

for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
		cout << ans[i][j] << ' ';
	}
	cout << endl;
}

while문이 끝나면 ans 행렬을 출력하면 된다.

#include <iostream>
#include <string>
#include <vector>

using namespace std;

long long n, b;
long long first[5][5];
long long ans[5][5];
long long p[5][5];

void solve(long long a[5][5], long long b[5][5]) {
	long long sam[5][5];

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			sam[i][j] = 0;
			for (int k = 0; k < n; k++) {
				sam[i][j] += a[i][k] * b[k][j];
			}
			sam[i][j] %= 1000;
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			a[i][j] = sam[i][j];
		}
	}
	
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> b;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> p[i][j];
		}
		ans[i][i] = 1;
	}

	while (b > 0) {
		if (b % 2 == 1) {
			solve(ans, p);
		}
		b /= 2;
		solve(p, p);
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << ans[i][j] << ' ';
		}
		cout << endl;
	}
}

전체코드다.