矩阵乘法快速幂矩阵乘法怎么快速幂啊?例如求斐波那契序列的第i位mod p,如何把那个2*2的矩阵用logn(n为相乘次数)的时间复杂度相乘n次……我笨.求详解
来源:学生作业帮助网 编辑:作业帮 时间:2024/06/20 03:59:49
![矩阵乘法快速幂矩阵乘法怎么快速幂啊?例如求斐波那契序列的第i位mod p,如何把那个2*2的矩阵用logn(n为相乘次数)的时间复杂度相乘n次……我笨.求详解](/uploads/image/z/5936585-41-5.jpg?t=%E7%9F%A9%E9%98%B5%E4%B9%98%E6%B3%95%E5%BF%AB%E9%80%9F%E5%B9%82%E7%9F%A9%E9%98%B5%E4%B9%98%E6%B3%95%E6%80%8E%E4%B9%88%E5%BF%AB%E9%80%9F%E5%B9%82%E5%95%8A%3F%E4%BE%8B%E5%A6%82%E6%B1%82%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E5%BA%8F%E5%88%97%E7%9A%84%E7%AC%ACi%E4%BD%8Dmod+p%2C%E5%A6%82%E4%BD%95%E6%8A%8A%E9%82%A3%E4%B8%AA2%2A2%E7%9A%84%E7%9F%A9%E9%98%B5%E7%94%A8logn%28n%E4%B8%BA%E7%9B%B8%E4%B9%98%E6%AC%A1%E6%95%B0%EF%BC%89%E7%9A%84%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%E7%9B%B8%E4%B9%98n%E6%AC%A1%E2%80%A6%E2%80%A6%E6%88%91%E7%AC%A8.%E6%B1%82%E8%AF%A6%E8%A7%A3)
矩阵乘法快速幂矩阵乘法怎么快速幂啊?例如求斐波那契序列的第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