题解 | #斐波那契数列#

题目链接

题目描述

经典的斐波那契数列 $F_n$ 定义如下： $F_n = \begin{cases} 1, & 1 \le n \le 2 \\ F_{n-1} + F_{n-2}, & n \ge 3 \end{cases}$

给定一个非常大的整数 $n$ ，计算 $F_n$ 在模 $10^9+7$ 意义下的值。

解题思路

当 $n$ 的值非常大时（例如 $n > 10^9$ ），直接使用循环递推计算 $F_n$ 的方法（时间复杂度为 $\mathcal{O}(n)$ ）将会超时。这是一个典型的可以使用矩阵快速幂进行优化的线性递推问题。

1. 构造递推矩阵

斐波那契数列的核心递推关系是 $F_n = F_{n-1} + F_{n-2}$ 。为了将其转化为矩阵形式，我们需要一个状态向量。我们选择向量 $\begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix}$ 。我们的目标是找到一个 $2 \times 2$ 的转移矩阵 $A$ ，使得：

\begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix} = A \cdot \begin{pmatrix} F_{n-1} \\ F_{n-2} \end{pmatrix}

根据递推公式，我们可以写出：

$F_n = 1 \cdot F_{n-1} + 1 \cdot F_{n-2}$
$F_{n-1} = 1 \cdot F_{n-1} + 0 \cdot F_{n-2}$

将这个线性方程组写成矩阵形式，我们得到：

\begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \cdot \begin{pmatrix} F_{n-1} \\ F_{n-2} \end{pmatrix}

这个 $\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$ 就是我们需要的转移矩阵，我们称之为 $A$ 。

2. 矩阵快速幂

利用上述关系，我们可以进行递推：

\begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix} = A \cdot \begin{pmatrix} F_{n-1} \\ F_{n-2} \end{pmatrix} = A^2 \cdot \begin{pmatrix} F_{n-2} \\ F_{n-3} \end{pmatrix} = \dots = A^{k} \cdot \begin{pmatrix} F_{n-k} \\ F_{n-k-1} \end{pmatrix}

为了求 $F_n$ ，我们可以从一个已知的初始状态开始。最方便的初始状态是 $(F_2, F_1)$ 。

\begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix} = A^{n-2} \cdot \begin{pmatrix} F_2 \\ F_1 \end{pmatrix}

根据题目定义， $F_1 = 1, F_2 = 1$ 。所以我们的任务变成了计算矩阵 $A^{n-2}$ ，然后与初始向量 $\begin{pmatrix} 1 \\ 1 \end{pmatrix}$ 相乘。

对于非常大的指数（如 $n-2$ ），计算 $A^{n-2}$ 可以使用快速幂算法。其原理与整数的快速幂完全相同：

若指数 $p$ 是偶数，则 $A^p = (A^{p/2})^2$ 。
若指数 $p$ 是奇数，则 $A^p = A \cdot A^{p-1}$ 。

通过这种方式，我们可以在 $\mathcal{O}(\log n)$ 次矩阵乘法内计算出 $A^{n-2}$ 。由于矩阵大小是常数（ $2 \times 2$ ），每次矩阵乘法的时间复杂度也是常数。

3. 算法流程

处理特殊情况：如果 $n \le 2$ ，根据定义直接返回 $1$ 。
定义转移矩阵 $A = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$ 。
使用矩阵快速幂算法计算 $B = A^{n-2} \pmod{10^9+7}$ 。
设 $B = \begin{pmatrix} b_{11} & b_{12} \\ b_{21} & b_{22} \end{pmatrix}$ 。
最终结果 $F_n$ 是 $B \cdot \begin{pmatrix} F_2 \\ F_1 \end{pmatrix}$ 这个结果向量的第一个分量。 $F_n = b_{11} \cdot F_2 + b_{12} \cdot F_1 = b_{11} \cdot 1 + b_{12} \cdot 1 = b_{11} + b_{12}$ 。
所有计算都在模 $10^9+7$ 的意义下进行。

代码

cpp
java
python

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 1000000007;

// 定义矩阵结构
struct Matrix {
    long long mat[2][2];

    Matrix() {
        mat[0][0] = mat[0][1] = mat[1][0] = mat[1][1] = 0;
    }
};

// 矩阵乘法
Matrix multiply(Matrix A, Matrix B) {
    Matrix C;
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                C.mat[i][j] = (C.mat[i][j] + A.mat[i][k] * B.mat[k][j]) % MOD;
            }
        }
    }
    return C;
}

// 矩阵快速幂
Matrix power(Matrix A, long long p) {
    Matrix result;
    result.mat[0][0] = result.mat[1][1] = 1; // 单位矩阵
    while (p > 0) {
        if (p % 2 == 1) {
            result = multiply(result, A);
        }
        A = multiply(A, A);
        p /= 2;
    }
    return result;
}

int main() {
    long long n;
    while (cin >> n) {
        if (n <= 2) {
            cout << 1 << endl;
            continue;
        }

        Matrix T;
        T.mat[0][0] = 1; T.mat[0][1] = 1;
        T.mat[1][0] = 1; T.mat[1][1] = 0;

        T = power(T, n - 2);

        long long ans = (T.mat[0][0] * 1 + T.mat[0][1] * 1) % MOD;
        cout << ans << endl;
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    static int MOD = 1000000007;

    // 矩阵乘法
    static long[][] multiply(long[][] a, long[][] b) {
        long[][] c = new long[2][2];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 2; k++) {
                    c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD;
                }
            }
        }
        return c;
    }

    // 矩阵快速幂
    static long[][] power(long[][] a, long p) {
        long[][] res = new long[2][2];
        res[0][0] = res[1][1] = 1; // 单位矩阵
        while (p > 0) {
            if ((p & 1) == 1) {
                res = multiply(res, a);
            }
            a = multiply(a, a);
            p >>= 1;
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLong()) {
            long n = sc.nextLong();
            if (n <= 2) {
                System.out.println(1);
                continue;
            }

            long[][] T = new long[2][2];
            T[0][0] = 1; T[0][1] = 1;
            T[1][0] = 1; T[1][1] = 0;

            T = power(T, n - 2);

            long ans = (T[0][0] * 1 + T[0][1] * 1) % MOD;
            System.out.println(ans);
        }
    }
}

import sys

MOD = 1000000007

# 矩阵乘法
def multiply(a, b):
    c = [[0, 0], [0, 0]]
    for i in range(2):
        for j in range(2):
            for k in range(2):
                c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD
    return c

# 矩阵快速幂
def power(a, p):
    res = [[1, 0], [0, 1]]  # 单位矩阵
    while p > 0:
        if p % 2 == 1:
            res = multiply(res, a)
        a = multiply(a, a)
        p //= 2
    return res

for line in sys.stdin:
    if not line.strip():
        continue
    n = int(line)
    
    if n <= 2:
        print(1)
        continue
        
    T = [[1, 1], [1, 0]]
    
    T = power(T, n - 2)
    
    # 结果是 T * [F(2), F(1)]^T 的第一个元素
    # F(n) = T[0][0]*F(2) + T[0][1]*F(1)
    ans = (T[0][0] * 1 + T[0][1] * 1) % MOD
    print(ans)

算法及复杂度

算法: 矩阵快速幂
时间复杂度: 矩阵的维度是 $2 \times 2$ ，为常数。矩阵快速幂需要进行 $\mathcal{O}(\log n)$ 次矩阵乘法，每次乘法的时间复杂度是 $\mathcal{O}(2^3) = \mathcal{O}(1)$ 。因此，总时间复杂度为 $\mathcal{O}(\log n)$ 。
空间复杂度: 算法需要存储几个 $2 \times 2$ 的矩阵用于计算，所需空间为常数。因此，空间复杂度为 $\mathcal{O}(1)$ 。