蓝桥杯基础练习VIP-矩阵乘法（矩阵快速幂） ----Momoc

解题思路:

矩阵乘法的公式：   

其实就是矩阵a的i行乘以矩阵b的j列。

快速幂贴上链接：https://blog.csdn.net/iwts_24/article/details/79780596

其实就是矩阵乘法套快速幂。
注意事项:
     因为求矩阵的N次幂 结果很大一般都取模，由于本题数据太水，嗯嗯。。。就不说了

    计算快速幂时要初始化单位矩阵。 矩阵a*单位矩阵e = 矩阵a

参考代码:

typedef long long ll;

#define N 101
struct Mat {
	ll m[N][N];
};
Mat input, e;
ll n, b;
//矩阵相乘
inline Mat Mat_mul(Mat x, Mat y) {
	Mat c;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			c.m[i][j] = 0;

	for (int i = 1; i <= n; i++) 
		for (int j = 1; j <= n; j++)
			for (int k = 1; k <= n; k++)
				c.m[i][j] = c.m[i][j]  + x.m[i][k] * y.m[k][j] ;
inline Mat Mat_pow(Mat a, ll y) {
    /*快速幂*/
	Mat ans=e; //单位矩阵
	while (y) {
		if (y & 1) 
			ans = Mat_mul(ans, a);
		a = Mat_mul(a, a);
		y >>= 1;
	}
	return ans;

}

int main() {

	cin >> n >> b;
	//cout << n <<" "<< b << endl;
	for (ll i = 1; i <= n; i++) {
		for (ll j = 1; j <= n; j++) {
			cin>> input.m[i][j];
		}
	}
	/*初始化单位矩阵*/
	for (ll i = 1; i <= n; i++)
		e.m[i][i] = 1;	
	Mat ans = Mat_pow(input, b);
	for (ll i = 1; i <= n; i++) {
		for (ll j = 1; j <= n; j++) {
			printf("%lld ", ans.m[i][j]);
		}
		printf("\n");
	}
	return 0;
}