행렬 제곱 (백준 10830)

안녕하세요. 오늘은 행렬을 제곱할 거예요.

문제

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

아이디어

그냥 A^B%C랑 비슷하게 하면 됩니다.
거듭제곱을 분할정복으로 하면 됩니다.
A^B의 값은 A^(B/2)의 값과 연관이 있다는것을 이용하면 됩니다.

소스코드

#include <iostream>
#include <vector>
#define ll long long
using namespace std;

ll N;
vector <vector <ll> > mul(vector <vector <ll> > arr, vector <vector <ll> > brr)
{
	ll i, j, k;
	vector <vector <ll> > Ans(N + 1, vector <ll>(N + 1, 0)); //N개의 0으로 채워져있는 N개의 벡터로 초기화 (뭔소리야)

	for (i = 1; i <= N; i++)
		for (j = 1; j <= N; j++)
			for (k = 1; k <= N; k++)
			{
				Ans[i][j] += arr[i][k] * brr[k][j];
				Ans[i][j] %= 1000;
			}
	return Ans;
}
vector <vector<ll> > mulmul(vector <vector <ll> > arr, ll num)
{
	if (num == 1) return arr;

	vector <vector <ll> > Ans(N, vector<ll>(N, 0));
	vector <vector <ll> > temp = mulmul(arr, num / 2);
	Ans = mul(temp,temp);
	if (num % 2 == 1) Ans = mul(Ans, arr);
	return Ans;
}

int main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	ll cnt, i, j;

	cin >> N >> cnt;
	vector <vector <ll> > v(N + 1, vector <ll>(N + 1, 0));

	for (i = 1; i <= N; i++)
		for (j = 1; j <= N; j++)
		{
			cin >> v[i][j];
			v[i][j] %= 1000;
		}

	v = mulmul(v, cnt);
	for (i = 1; i <= N; i++)
	{
		for (j = 1; j <= N; j++)
			cout << v[i][j] << ' ';
		cout << "\n";
	}
}

감사합니다.