蓝桥杯 - [基础练习VIP]矩阵乘法(矩阵快速幂)
发布日期:2021-07-01 00:18:24
浏览次数:3
分类:技术文章
本文共 1075 字,大约阅读时间需要 3 分钟。
题目链接:
时间限制:1.0s 内存限制:512.0MB问题描述
给定一个N阶矩阵A,输出A的M次幂(M是非负整数)
例如:A =
1 2 3 4A的2次幂:
7 10
15 22输入格式
第一行是一个正整数N、M(1< =N< =30, 0< =M< =5),表示矩阵A的阶数和要求的幂数
接下来N行,每行N个绝对值不超过10的非负整数,描述矩阵A的值输出格式
输出共N行,每行N个整数,表示A的M次幂所对应的矩阵。相邻的数之间用一个空格隔开
样例输入
2 2
1 2 3 4
样例输出
7 10
15 22
解题思路
线性代数,模拟矩阵相乘的过程。
#includeusing namespace std;typedef long long ll;struct Mat { ll m[35][35];}ans, a;int n, m;Mat Mul(Mat a, Mat b) { Mat c; memset(c.m, 0, sizeof(c.m)); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) for (int k = 0; k < n; k++) c.m[i][j] += a.m[i][k] * b.m[k][j]; return c;}int main() { scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%d", &a.m[i][j]); for (int i = 0; i < n; i++) ans.m[i][i] = 1; while (m) {//矩阵快速幂 if (m & 1) ans = Mul(ans, a); a = Mul(a, a); m >>= 1; } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) printf("%d ", ans.m[i][j]); printf("\n"); } return 0;}
转载地址:https://lzyws739307453.blog.csdn.net/article/details/90318403 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
第一次来,支持一个
[***.219.124.196]2024年05月01日 03时49分35秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
linux 查看分区和文件大小
2019-04-30
技术转管理?这些“坑”你要绕道走
2019-04-30
领域驱动设计(DDD)前夜:面向对象思想
2019-04-30
Camera驱动调试小记
2019-04-30
四线触摸屏原理
2019-04-30
C/C++如何返回一个数组/指针
2019-04-30
腾讯AI语音识别API踩坑记录
2019-04-30
安装openrave 0.9的各种依赖包
2019-05-01
@FeignClient注解的重复名称解决
2019-05-01
java.net.BindException: 无法指定被请求的地址
2019-05-01
scala list
2019-05-01
svn服务器安装
2019-05-01
spark 笔记1
2019-05-01
shell dirname basename
2019-05-01
未来已至,5G加持下的云游戏将走向何方?
2019-05-01
计算机网络 —— 网络层 1.
2019-05-01
Android 之 ContentProvider 与 ContentResolver
2019-05-01
【接口自动化】
2019-05-01
推荐一位川大零基础转行 Python 的人生勇士
2019-05-01
Python解惑之:True与False
2019-05-01