本文先是给出快速幂的原理，又由一道例题明确快速幂的Python代码模版；而后给出矩阵快速幂的原理（介绍了矩阵相乘，对没学过线代者友好），和矩阵快速幂的模版。再给出快速幂和矩阵快速幂相关的题单。
目录
快速幂原理
快速幂Python代码模版
蓝桥oj1514：快速幂
题目描述
输入描述
输出描述
输入输出样例
求解
矩阵快速幂原理
矩阵相乘
蓝桥oj1550：矩阵相乘
题目描述
输入描述
输出描述
输入输出样例
求解
矩阵快速幂
矩阵快速幂Python代码模版
题单
快速幂原理
对于一个正整数，给定正整数
，计算
的复杂度是
。
如果把n用二进制进行编码，可降低复杂度为。
比如当n=5时，二进制编码为101，只需做三次循环。用ans存取的值，初始赋值为1。变量temp初始值赋值为a，每个循环中ans*=temp，循环末尾就把temp*=a。
快速幂Python代码模版
通过一道模版题给出。
蓝桥oj1514：快速幂
题目描述
输入 b，p，k 的值，求 b^(p)modk 的值。其中2≤b,p,k≤10^9 。
输入描述
三个整数 b,p,k。
输出描述
输出 b^(p)modk=s，s 为运算结果。
输入输出样例
示例
输入
2 10 9
输出
7求解
把n看成二进制，逐个处理末尾的一项。
另外，根据取模的性质有。
def fast_pow(a,n,mod):ans=1while n:if(n&1):ans=ans*a%moda=a*a%modn>>=1return ansb,p,k=map(int,input().split())
print(fast_pow(b,p,k))
矩阵快速幂原理
矩阵相乘
矩阵相乘C=AB:
要求A的列数等于B的行数。下面给出一道例题。
蓝桥oj1550：矩阵相乘
题目描述
小明最近刚刚学习了矩阵乘法，但是他计算的速度太慢，于是他希望你能帮他写一个矩阵乘法的运算器。
输入描述
输入的第一行包含三个正整数N,M,K，表示一个 NM的矩阵乘以一个MK的矩阵。接下来N行，每行M个整数，表示第一个矩阵。再接下来的M行，每行K个整数，表示第二个矩阵。
0<N,M,K≤100,0≤ 矩阵中的每个数 ≤1000。
输出描述
输出有 N 行，每行 K 个整数，表示矩阵乘法的结果。
输入输出样例
示例
输入
2 1 3
1
2
1 2 3
输出
1 2 3
2 4 6求解
n,m,k=map(int,input().split())
A=[]
B=[]
C=[[0]*k for i in range(n)]
for i in range(n): A.append(list(map(int,input().split())))
for i in range(m): B.append(list(map(int,input().split())))
for i in range(n):for j in range(m):for l in range(k): C[i][l]+=A[i][j]*B[j][l]
for i in range(n):for j in range(k): print(C[i][j],end=" ")print()
矩阵快速幂
若矩阵A是N*N的方阵，它可以自乘，把n个A相乘记。
矩阵快速幂的时间复杂度：。
矩阵快速幂Python代码模版
代码逻辑基本与快速幂一样，n%2与n&1等价。只是多了矩阵相乘的函数，以及ans初始化为单位对角阵而已。
def multi(A,B):m1,n1=len(A),len(A[0])m2,n2=len(B),len(B[0])if n1!=m2:return NoneC=[[0]*n2 for i in range(m1)]for i in range(m1):for k in range(n1):for j in range(n2):C[i][j]+=A[i][k]*B[k][j]return Cdef power(A,n):N=len(A)ans=[[0]*N for i in range(N)]for i in range(N):ans[i][i]=1while n:if n%2:ans=multi(ans,A)A=multi(A,A)n//=2return ans题单
1551：方阵幂次（纯纯模版题）
132：垒骰子
1552：新型斐波那契数列
933：迷路
98：包子凑数
