题解 | 波斐契那数列

1. python3代码

import sys

MOD = 10**9 + 7

# 3x3 矩阵乘法 (mod MOD)
def mat_mul(A, B):
    return [
        [(A[0][0]*B[0][j] + A[0][1]*B[1][j] + A[0][2]*B[2][j]) % MOD for j in range(3)],
        [(A[1][0]*B[0][j] + A[1][1]*B[1][j] + A[1][2]*B[2][j]) % MOD for j in range(3)],
        [(A[2][0]*B[0][j] + A[2][1]*B[1][j] + A[2][2]*B[2][j]) % MOD for j in range(3)]
    ]
    
# 矩阵快速幂
def mat_pow(M, p):
    # 单位矩阵
    res = [[1,0,0],[0,1,0],[0,0,1]]
    base = M
    while p:
        if p & 1:
            res = mat_mul(res, base)
        base = mat_mul(base, base)
        p >>= 1
    return res

# 读入数据：先读 T，再依次读每个 n
first_line = True
t = 0
cnt = 0
for line in sys.stdin:
    line = line.strip()
    if not line:
        continue
    if first_line:
        t = int(line)
        first_line = False
        continue

    n = int(line)
    cnt += 1

    if n <= 3:
        print("1")
    else:
        # 转移矩阵
        M = [
            [1, 0, 1],
            [1, 0, 0],
            [0, 1, 0]
        ]
        Mp = mat_pow(M, n - 3)
        # 初始向量 [a3, a2, a1] = [1,1,1]
        an = (Mp[0][0] + Mp[0][1] + Mp[0][2]) % MOD
        print(str(an))

    if cnt == t:
        break

2. 数学原理

直接递推计算 a_n 需要 O(n) 时间，但 n 最大可达 2 × 10^9，无法逐个计算。

注意到递推式是线性齐次的，可以用矩阵快速幂将时间复杂度降到 O(log n)。

5. 矩阵快速幂

为了高效计算 M^{n-3}，使用快速幂算法：

• 将指数 p = n-3 二进制分解。
• 维护一个结果矩阵 res（初始为单位矩阵）和底数矩阵 base初始为 M。
• 遍历 p 的二进制位：若当前位为 1，则 res = res × base；然后 base = base × base，准备下一位。
• 每次矩阵乘法 3×3 时间复杂度 O(3^3) = O(27))常数，总体复杂度 O(log n)。

由于题目要求结果模 10^9+7，所有乘法均取模。

6. 复杂度分析

• 每个询问：矩阵快速幂 O(log n) 次乘法，每次乘法 O(27) 操作，常数极小。
• 总时间复杂度：O(T log n)，对于 T <= 100 完全可行。
• 空间复杂度：仅存储常数的几个矩阵和结果列表。

PS: 这编辑器对LaTeX数学公式的支持都没有，太难弄了！矩阵部分只能用截图代替，大大降低我分享的动力