1907: 蓝桥杯算法提高VIP-递推求值（Python3）矩阵快速幂

解题思路:
同斐波那契，利用通项公式推导并写为矩阵乘法形式，然后利用快速幂计算。

注意事项:
矩阵乘法时就要取余，否则超时。

参考代码:

def matrix_mul(A, B):
    return [[sum(a * b % 99999999 for a, b in zip(col, row)) % 99999999 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 & 1:
            return matrix_mul(matrix_mul(y, y), A)
        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]]
a = matrix_mul(matrix_pow(matrix, int(input()) - 1), ini)
print(a[-3][0] % 99999999, a[-2][0] % 99999999, sep='\n')