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