作业帮矩阵乘法快速幂矩阵乘法怎么快速幂啊?例如求斐波那契序列的第i位mod p,如何把那个2*2的矩阵用logn(n为相乘次数）的时间复杂度相乘n次……我笨.求详解
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/13 08:11:49
矩阵乘法快速幂矩阵乘法怎么快速幂啊?例如求斐波那契序列的第i位mod p,如何把那个2*2的矩阵用logn(n为相乘次数）的时间复杂度相乘n次……我笨.求详解
矩阵乘法快速幂
矩阵乘法怎么快速幂啊?例如求斐波那契序列的第i位mod p,如何把那个2*2的矩阵用logn(n为相乘次数）的时间复杂度相乘n次……我笨.求详解
矩阵乘法快速幂矩阵乘法怎么快速幂啊?例如求斐波那契序列的第i位mod p,如何把那个2*2的矩阵用logn(n为相乘次数）的时间复杂度相乘n次……我笨.求详解
A^2k = (A^2)^k,A^(2k+1) = (A^2)^k*A
也就是对于n规模的的,可以化到n/2