矩阵快速幂python

矩阵快速幂算法是一种用于高效计算矩阵的乘方的方法。通过使用递归和分治策略，可以将矩阵的乘方计算复杂度从O(n)降低到O(logn)。在Python中，可以使用以下代码实现矩阵快速幂算法：

def matrix_mul(A, B):
    # 矩阵乘法函数，返回两个矩阵相乘的值
    return [[sum(a * b for a, b in zip(col, row)) for col in zip(*B)] for row in A]

def matrix_pow(A, n):
    size_ = len(A)
    if n == 0:
        # 返回单位矩阵
        res = [[0 for _ in range(size_)] for _ in range(size_)]
        for i in range(size_):
            res[i][i] = 1
        return res
    elif n == 1:
        # 返回自己
        return A
    else:
        y = matrix_pow(A, n // 2)
        if n % 2 == 1:
            # 要乘
            return matrix_mul(matrix_mul(y, y), A)
        else:
            # 不乘
            return matrix_mul(y, y)

# 示例矩阵
matrix = [[0, 1, 0, 0, 2, 0, 5], 
          [1, 0, 0, 0, 3, 2, 3], 
          [1, 0, 0, 0, 0, 0, 0], 
          [0, 1, 0, 0, 0, 0, 0], 
          [0, 0, 1, 0, 0, 0, 0], 
          [0, 0, 0, 1, 0, 0, 0], 
          [0, 0, 0, 0, 0, 0, 1]]

# 初始值
ini = [[6], [5], [1], [4], [2], [3], [1]]

# 计算第n个值
n = int(input("请输入n的值："))
result = matrix_mul(matrix_pow(matrix, n - 1), ini)

# 输出结果
print(result[-3][0] % 99999999)
print(result[-2][0] % 99999999)