【藍橋杯】基礎練習 矩陣乘法

問題描述

　　給定一個 N N N階矩陣 A A A，輸出 A A A的 M M M次幂（ M M M是非負整數）

　　例如：

　　 A A A =

　　1 2

　　3 4

　　 A A A的2次幂

　　7 10

　　15 22

輸入格式

　　第一行是一個正整數 N N N、 M M M（1<= N N N<=30, 0<= M M M<=5），表示矩陣 A A A的階數和要求的幂數

　　接下來 N N N行，每行 N N N個絕對值不超過10的非負整數，描述矩陣 A A A的值

輸出格式

　　輸出共 N N N行，每行 N N N個整數，表示 A A A的 M M M次幂所對應的矩陣。相鄰的數之間用一個空格隔開

樣例輸入

2 2

1 2

3 4

樣例輸出

7 10

15 22

【内心 o s os os：看到這個題目，就想起大佬常說的矩陣快速幂，但，，奈何不會呀！隻能老老實實用線代中的隻是解決了(其實還是偷學了一點點應用到代碼中)】

個人思路：用一個結構體存儲二維數組，即矩陣，然後就直接矩陣乘法了，感覺還是挺簡單的；需要注意一下對于幂數的判斷， m = 0 m = 0 m=0或 m = 1 m = 1 m=1這兩種特殊情況要單獨處理

#include <iostream>
#include <cstdio>
#include <string.h> 
#include <algorithm>
using namespace std;
int n,m;
struct node {
	int a[35][35];
	node () {
		memset(a, 0, sizeof(a));
	}
};
node A,res;
//矩陣乘法
node mul(node ans, node ant) {
	node t;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			for (int k = 0; k < n; ++k) {
				t.a[i][j] += ans.a[i][k] * ant.a[k][j];
			}
		}
	}
	return t;
}
//幂
node mul_m(node ans) {
	node h,t;
	t = ans;
	for (int i = 0; i < m - 1; ++i) {
		h = mul(t, ans);
		t = h;
	}
	return t;
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			cin >> A.a[i][j];
		}
	}
	//原矩陣
	if (m == 1) {
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				cout << A.a[i][j] << " ";
			}
			cout << endl;
		}
	}
	//機關矩陣
	else if (m == 0) {
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++){
				if(i==j)
					cout << 1 << " ";
				else
					cout << 0 << " ";
			}
			cout << endl;
		}
	}
	else {
		node result;
		result = mul_m(A);
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				cout << result.a[i][j] << " ";
			}
			cout << endl;
		}
	}
	return 0;	
}