hdu4965 巧用矩阵乘法结合律
矩阵 乘法 巧用
2023-09-11 14:14:00 时间
题意:
给两个矩阵,n*m的矩阵A,和m*n的矩阵B,
求(A*B)^(n*n)其中 m<=6,n<=1000。
思路:
一开始直接模拟,写了个矩阵快速幂,超时了,因为A*B后得到的是1000*1000的矩阵,做乘法直接超时了,后来写了个这样的
(A*B)^(n*n) = (A*B)*(A*B)*(A*B)...
= A * (B*A)*(B*A)*(B*A)...*B
给两个矩阵,n*m的矩阵A,和m*n的矩阵B,
求(A*B)^(n*n)其中 m<=6,n<=1000。
思路:
一开始直接模拟,写了个矩阵快速幂,超时了,因为A*B后得到的是1000*1000的矩阵,做乘法直接超时了,后来写了个这样的
(A*B)^(n*n) = (A*B)*(A*B)*(A*B)...
= A * (B*A)*(B*A)*(B*A)...*B
矩阵虽然没有交换律但是有结合律,我们直接先B*A(得到的是一个最大6*6的矩阵)然后快速幂,然后再A * BA^(n*n-1) * B这样就行了,然后又超时了,算了很多次,感觉不可能超时,但还是超时了,原因就是我所有的矩阵用的都是mat[1002][1002]为了方便我都开结构体了,结果各种超时,最后没办法了,全都开数组,然后去模拟,A[1002][8],B[8][1002],BA[8][8]...,这样就AC了,难道开大的数组也会浪费很多时间?(这个地方头一次碰到)。
#include<stdio.h> #include<string.h> typedef struct { int mat[8][8]; }AA; int A[1002][8] ,B[8][1002] ,C[1002][1002]; int nmm[1002][8]; AA mat_matba(int n ,int m) { AA c; memset(c.mat ,0 ,sizeof(c.mat)); for(int k = 1 ;k <= n ;k ++) for(int i = 1 ;i <= m ;i ++) if(B[i][k]) for(int j = 1 ;j <= m ;j ++) c.mat[i][j] = (c.mat[i][j] + B[i][k] * A[k][j])%6 ; return c; } AA mat_mat(AA a ,AA b ,int n) { AA c; memset(c.mat ,0 ,sizeof(c.mat)); for(int k = 1 ;k <= n ;k ++) for(int i = 1 ;i <= n ;i ++) if(a.mat[i][k]) for(int j = 1 ;j <= n ;j ++) c.mat[i][j] = (c.mat[i][j] + a.mat[i][k] * b.mat[k][j]) % 6; return c; } AA quick_mat(AA a ,int b ,int n) { AA c; memset(c.mat ,0 ,sizeof(c.mat)); for(int i = 1 ;i <= n ;i ++) c.mat[i][i] = 1; while(b) { if(b&1) c = mat_mat(c ,a ,n); a = mat_mat(a ,a ,n); b >>= 1; } return c; } void mat_matnmm(AA mm ,int n ,int m) { memset(nmm ,0 ,sizeof(nmm)); for(int k = 1 ;k <= m ;k ++) for(int i = 1 ;i <= n ;i ++) if(A[i][k]) for(int j = 1 ;j <= m ;j ++) nmm[i][j] = (nmm[i][j] + A[i][k] * mm.mat[k][j]) % 6; } void mat_matnmmn(int n ,int m) { memset(C ,0 ,sizeof(C)); for(int k = 1 ;k <= m ;k ++) for(int i = 1 ;i <= n ;i ++) for(int j = 1 ;j <= n ;j ++) C[i][j] = (C[i][j] + nmm[i][k] * B[k][j]) % 6; } int main () { int n ,m ,i ,j; while(~scanf("%d %d" ,&n ,&m) && n + m) { for(i = 1 ;i <= n ;i ++) for(j = 1 ;j <= m ;j ++) scanf("%d" ,&A[i][j]); for(i = 1 ;i <= m ;i ++) for(j = 1 ;j <= n ;j ++) scanf("%d" ,&B[i][j]); AA c = mat_matba(n ,m); AA ban = quick_mat(c ,n*n-1 ,m); mat_matnmm(ban ,n ,m); mat_matnmmn(n ,m); int sum = 0; for(i = 1 ;i <= n ;i ++) for(j = 1 ;j <= n ;j ++) sum += C[i][j]; printf("%d\n" ,sum); } return 0; }
相关文章
- Java实现 蓝桥杯 算法提高 矩阵翻转
- Java实现 蓝桥杯 算法训练 矩阵乘法
- Java实现 蓝桥杯 算法训练 矩阵乘法
- 输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字
- LeetCode(59):螺旋矩阵 II
- LeetCode-1605. 给定行和列的和求可行矩阵【贪心,矩阵】
- 机器学习笔记 - 构建推荐系统(4) 用于协同过滤的矩阵分解
- Open3D 四元数、欧拉角、旋转向量转旋转矩阵
- 理解矩阵乘法
- 理解矩阵乘法
- 【[Offer收割]编程练习赛13 D】骑士游历(矩阵模板,乘法,加法,乘方)
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-86 矩阵乘法
- 二流四流神经网路(模型融合矩阵乘法理论实践)
- zoj 2317 Nice Patterns Strike Back(矩阵乘法)
- 【华为OD机试Python实现】HJ69 矩阵乘法(中等)
- 模拟法螺旋遍历矩阵:54.螺旋矩阵(Kotlin)
- 【MATLAB】矩阵操作 ( 矩阵下标 | 矩阵下标排列规则 )
- [转]如何理解矩阵乘法的规则
- torch.spmm矩阵乘法
- pytorch 中矩阵乘法
- 正定矩阵 和 半正定矩阵
- 27 | SIMD:如何加速矩阵乘法?
- geo读取表达矩阵 RNA-seq R语言部分(表达矩阵合并及id转换)
- 基于FPGA的脉动阵列矩阵乘法
- system verilog实现矩阵乘法
- HDU 4914 Linear recursive sequence(矩阵乘法递推的优化)
- MATLAB学习笔记(二)——主要是MATLAB的矩阵知识
- 非监督异常点检测算法总结——没有想到矩阵分解和编码解码器也是一种思路
- CNN卷积神经网络_深度残差网络 ResNet——解决神经网络过深反而引起误差增加的根本问题,Highway NetWork 则允许保留一定比例的原始输入 x。(这种思想在inception模型也有,例如卷积是concat并行,而不是串行)这样前面一层的信息,有一定比例可以不经过矩阵乘法和非线性变换,直接传输到下一层,仿佛一条信息高速公路,因此得名Highway Network
- YOLOv7改进Transformer主干系列:首发结合CotNet Transformer结构,指导动态注意力矩阵的学习,增强视觉表示能力。