BOJ 10830 : 행렬 제곱

알고리즘 문제 전체 링크

 

www.acmicpc.net/problem/10830

 

 

곱셈 문제처럼 이진수의 원리를 그대로 적용하여 해결하였다.

행렬의 곱은 A = B * C 일 때, A[r][c] = ∑B[r][k] * B[k][c]를 이용한다.

#include <stdio.h>

typedef unsigned long long int ull;

int N;
ull B;

int matrix[7][7];
int ans[7][7];

void multiply(int matrixA[][7], int matrixB[][7])
{
	int temp[7][7] = { 0 };

	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			temp[r][c] = 0;
			for (int k = 1; k <= N;k++)
				temp[r][c] += matrixA[r][k] * matrixB[k][c];
		}
	}

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			matrixA[r][c] = temp[r][c] % 1000;
}

int main(void)
{
	scanf("%d %lld", &N, &B);

	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			scanf("%d", &matrix[r][c]);
			if (r == c) ans[r][c] = 1;
		}
	}

	while (B)
	{
		if (B & 1) multiply(ans, matrix);

		multiply(matrix, matrix);
		B /= 2;
	}

	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
			printf("%d ", ans[r][c]);
		putchar('\n');
	}

	return 0;
}