蓝桥杯 方阵幂次（矩阵快速幂模板题）

蓝桥杯 方阵幂次（矩阵快速幂模板题）

题目描述

给定一个 $N$ 阶矩阵 A 和一个常数 $M$，请你输出 A 的 $M$ 次幂。

输入描述

输入第一行包含两个整数 $N$,$M$。

接下来 $N$行，每行包含 $N$个数，表示矩阵 A。

$1\le N\le 30$，$0\le M\le 5$，矩阵中的每个数 $\le 5$。

输出描述

输出有 $N$ 行，每行 $N$ 个整数，表示 A M A^M AM。

输入输出样例

示例

输入

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 = 0for z in range(m):tmp += A[i][z]*B[z][j]ans[i][j] = tmpreturn ansdef fast_pow(A,M):N = len(A)res = [[0]*N for _ in range(N)]for i in range(N): res[i][i] = 1while M:if M&1:res=multi(res,A)A = multi(A,A)M >>= 1return resres = fast_pow(a,m)
for i in range(n):for j in range(n):print(res[i][j],end=" ")print()

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！