c++ 백준_10830_"행렬 제곱"

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

10830번: 행렬 제곱

​

문제 11444 를 풀고 나서

바로 행렬 제곱이 눈에 보이길래 해결하였다.

​

근데 문제를 풀 때 자꾸 특정 퍼센트에서 틀리길래 뭐지 싶었는데

제일 처음 원소값으로 1000이 입력되고 만약 B가 1이라면

해당 원소값은 0이 되어야하는데

1000이 그대로 나왔다.

​

해당 처리를 안해서 몇번 틀렸다.

 

#include <iostream>
#include <vector>
using namespace std;

typedef unsigned long long type;

#define MOD 1000

vector<vector<type>> base;
type N, B;


vector<vector<type>> arrMult(vector<vector<type>> a, vector<vector<type>> b) {

	vector<vector<type>> arr(N,vector<type>(N,0));

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			type result = 0;
			for (int k = 0; k < N; k++) {
				result += (a[i][k] * b[k][j]) % MOD;
			}
			arr[i][j] = result % MOD;
		}
	}

	return arr;
}

vector<vector<type>> powarr(type B) {
	
	if (B == 1)
		return base;
	
	vector<vector<type>> temp = powarr(B / 2);
	vector<vector<type>> multResult = arrMult(temp, temp);

	if (B % 2 == 0) {
		return multResult;
	}
	else {
		return arrMult(multResult, base);
	}

}

int main(void) {

	cin >> N >> B;


	base.resize(N, vector<type>(N));

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> base[i][j];
		}
	}

	vector<vector<type>> ans = powarr(B);

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cout << ans[i][j] % MOD<<" ";
		}
		cout << "\n";
	}

}