蓝桥杯基础练习VIP-矩阵乘法矩阵快速幂(详细解释)

3443 阅读 1 评论 0 点赞

##1.快速幂
首先给出一段快速幂模板:
```Python
def fastpow(base,n)
	ans=1
	while(n):
		ifn&1:
			ans*=base
		base*=base
		n>>=1
	return ans
```
计算$$x^{n}$$通常需要 n次乘法, 时间复杂度为 O(n),当 n 非常大的时候, 运算效率很低.快速幂是通过把n转化为二进制来实现的. 例如: 计算$$x^{14}$$ ,14 可以用二进制表示为:14=(1110)$$_{2}$$=1 x 2$$^{3}$$+1 x 2$$^{2}$$+1 x 2$$^{1}$$+1 x 2$$^{0}$$那么对应的乘法可以表示为:$$x^{14}$$=$$x^{2^3}$$*$$x^{2^2}$$*$$x^{2^1}$$转换后乘法运算次数减少, 每次计算 $$x^{2^n}$$, 再决定是否将这个数字加入到最终结果里面去. 代码如下:
```python
def fpowx(x, n):
    res = 1
    while n:
        if n & 1:
            res = res * x
        # compute x^2 x^4 x^8
        x *= x
        n >>= 1
    return res

```
##2. 矩阵快速幂
###2.1矩阵乘法
对于矩阵乘法,对于学习过线性代数的同学来说再简单不过了,这里就不在赘述,直接上代码:

```Python
def multi(matrix_a,matrix_b):
    #对于a*b和b*c的矩阵,得到的规模是a*c
    matrix_result=[[0 for _ in range(len(matrix_b[0]))] for _ in range(len(matrix_a))]
    for i in range(len(matrix_a)):
        for j in range(len(matrix_b[0])):
            #这里len(matrix_b)也可以换成len(matrix_a[0])
            for k in range(len(matrix_b)):
                matrix_result[i][j]+=matrix_a[i][k]*matrix_b[k][j]
    return matrix_result
```
###2.2矩阵快速幂
对于一个方阵 A, 也可以使用快速幂计算,相对于一般的快速幂，矩阵快速幂仅仅是把他的底数和乘数换成了矩阵形式，而相应的乘法运算什么的也遵循矩阵的运算法则 例如:$$A^{14}$$=$$A^{8}\times$$*$$A^{4}\times$$ *$$A^{2}\times$$ $$E$$ 其中E是和方阵A规模相同的单位矩阵,Python 代码如下:
```python
# 求和matrix规模相同的单位矩阵E
def unit_1(n):
    #print('unit进来了')
    #初始化为0
    E=[[0 for _  in range(n)]for _ in range(n)]
    #对角线为1
    for i in range(n):
        E[i][i]=1
    #print(E)
    return E
#矩阵快速幂
def quick_multi(matrix,m):
    #print('quick进来')
    res=unit_1(len(matrix))
    while m:
        if m&1:
            res=multi(res,matrix)
        matrix=multi(matrix,matrix)
        m=m>>1
    #print('quick结束')
    return res
```
最终提交代码如下:
```python
#输入方阵的大小(n*n) 和幂m
n,m=map(int,input().split())
# 输入数据生成矩阵
matrix=[]
for _ in range(n):
    matrix.append(list(map(int,input().split())))
#矩阵matrix_a和矩阵matrix_b相乘得到matrix_result
def multi(matrix_a,matrix_b):
    #对于a*b和b*c的矩阵,得到的规模是a*c
    matrix_result=[[0 for _ in range(len(matrix_b[0]))] for _ in range(len(matrix_a))]
    for i in range(len(matrix_a)):
        for j in range(len(matrix_b[0])):
            #这里len(matrix_b)也可以换成len(matrix_a[0])
            for k in range(len(matrix_b)):
                matrix_result[i][j]+=matrix_a[i][k]*matrix_b[k][j]
    return matrix_result
# 求和matrix规模相同的单位矩阵E
def unit_1(n):
    #print('unit进来了')
    #初始化为0
    E=[[0 for _  in range(n)]for _ in range(n)]
    #对角线为1
    for i in range(n):
        E[i][i]=1
    #print(E)
    return E
#矩阵快速幂
def quick_multi(matrix,m):
    #print('quick进来')
    res=unit_1(len(matrix))
    while m:
        if m&1:
            res=multi(res,matrix)
        matrix=multi(matrix,matrix)
        m=m>>1
    #print('quick结束')
    return res
#输出
for r in quick_multi(matrix,m):
    print(' '.join([str(i) for i in r]))

```

0.0分

11 人评分

本文分类：题解列表
浏览次数：3443 次浏览
发布日期：2021-03-18 19:07:15
本文链接：https://blog.dotcpp.com/a/77575

上一篇 > 蓝桥杯算法提高VIP-夺宝奇兵
下一篇 > 不是题解的题解

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

蓝桥杯基础练习VIP-矩阵乘法矩阵快速幂(详细解释)

评论列表共有 1 条评论

发表评论取消回复

蓝桥杯基础练习VIP-矩阵乘法 矩阵快速幂(详细解释)

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 1 条评论

发表评论 取消回复

蓝桥杯基础练习VIP-矩阵乘法矩阵快速幂(详细解释)

评论列表共有 1 条评论

发表评论取消回复