[伯俊]10830行列平方

質問する
N*Nの大きさのマトリクスAが与えられる.この場合、AのB乗を求めるプログラムを作成してください.数が大きくなる可能性があるので、A^Bの各要素を1000の残りで割って出力します.
入力
第1行は、行列のサイズNおよびBを与える.(2 ≤ N ≤ 5, 1 ≤ B ≤ 100,000,000,000)
2行目から、行列の各要素をN行に付与する.マトリクス内の各要素は、1000以下の自然数または0です.
しゅつりょく
1行目からN行目までは、出力マトリクスAにBを乗じた結果が出力される.
入力例1
2 5
1 2
3 4
サンプル出力1
69 558
337 406
Concept
Bの大きさは非常に大きく、Brute Forceは使えないかもしれません.n/2を再帰再呼び出しで割った分割征服を用いる.
Code

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

int** arr;
int n;

//두 행렬을 곱해주는 함수
int** multi(int** arr, int** arr2){
	//int tmp[5][5] = { 0 };
	int** tmp;
	tmp = new int* [n];
	for (int i = 0; i < n; i++) {
		tmp[i] = new int[n];
	}

	for (int i = 0; i < n; i++) 
		for (int j = 0; j < n; j++) tmp[i][j] = 0;
		
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < n; k++) {
				tmp[i][j] += (arr[i][k] * arr2[k][j])%1000;
			}
		}
	}
	return tmp;

}
// 지수를 쪼개어 곱하는 기능 담당
int** pow(long long n){
	if (n == 1) return arr;
	else if (n % 2 == 1) return multi(pow(n-1), arr);
	else {
		int** tmp = pow(n / 2);
		return multi(tmp, tmp);
	}
}


int main() {
	long long b;
	cin >> n >> b;

	
	arr = new int* [n];
	for (int i = 0; i < n; i++) {
		arr[i] = new int[n];
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
		}
	}
	int** result = pow(b);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout<< result[i][j]%1000<<' ';
		}
		cout << endl;
	}
}

Comment
思い出すのは簡単だが、実施するのは容易ではない.
2 D配列を渡すためには、動的割り当てを行わなければなりません.
初期分が1000という条件は見られなかったので、不要な時間がかかりました.

else {
		int** tmp = pow(n / 2);
		return multi(pow(n / 2), pow(n / 2));
	}

前述したように、pow演算2回の値を返すと、計算が1回繰り返され、タイムアウトやメモリオーバーフローが発生します.ご留意ください.