蓝桥杯 方阵幂次（矩阵快速幂模板题）
题目描述
输入第一行包含两个整数 N M。
接下来 N行，每行包含 N 个数，表示矩阵 A。
1 ≤ N ≤ 30 ，0 ≤ M ≤ 5 ，矩阵中的每个数 ≤ 5
输出描述
输出有 N 行，每行 N 个整数，表示
输入输出样例
示例
输入
2 2 1 2 3 4
输出
7 10 15 22
运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
标签: 矩阵快速幂
思路
这是一道矩阵快速幂的模板题，可以理由矩阵快速幂来解决
import os import sys # 请在此输入您的代码 n,m = map(int,input().split()) a = [] for i in range(n): a.append(list(map(int,input().split()))) def multi(A,B): n,m,k = len(A),len(A[0]),len(B[0]) ans = [[0]*k for _ in range(n)] for i in range(n): for j in range(k): tmp = 0 for z in range(m): tmp += A[i][z]*B[z][j] ans[i][j] = tmp return ans def fast_pow(A,M): N = len(A) res = [[0]*N for _ in range(N)] for i in range(N): res[i][i] = 1 while M: if M&1: res=multi(res,A) A = multi(A,A) M >>= 1 return res res = fast_pow(a,m) for i in range(n): for j in range(n): print(res[i][j],end=" ") print()
