题解 | #斐波那契数列#

题目链接

题目描述

斐波那契数列（Fibonacci Sequence）定义如下： F(1)=1, F(2)=1；对于 n>2，有 F(n)=F(n-1)+F(n-2)。给定一个正整数 n，请你输出 F(n) 的值。由于这个结果可能很大，你只需要输出这个结果对 1000000007 取模后的结果即可。

输入描述: 在一行上输入一个整数 n。

输出描述: 输出一个整数，表示 F(n) 的值。

解题思路

这道题是经典的斐波那契数列问题，但需要注意的是，输入 n 的范围可能很大，常规的递推或递归解法可能会超时。

方法一：动态规划 (O(N))

当 n 的值不大时（例如 n <= 10^7），我们可以使用动态规划（迭代）的方式来解决。定义一个数组 dp，dp[i] 表示 F(i) 的值。状态转移方程为 dp[i] = (dp[i-1] + dp[i-2]) % 1000000007。基础情况是 dp[1] = 1, dp[2] = 1。我们只需要一个大小为 3 的滚动数组或者两个变量就可以完成递推，空间复杂度可以优化到 O(1)。

这个方法虽然简单，但当 n 达到 10^9 或 10^{18} 级别时，线性时间复杂度的算法会超时。

方法二：矩阵快速幂 (O(log N))

当 n 非常大时，我们需要一个更高效的算法。斐波那契数列的递推关系可以表示为矩阵形式。我们有递推式： $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} \begin{pmatrix} F(n-1) \\ F(n-2) \end{pmatrix}$

令转移矩阵 $M = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$ 。为了建立一个普适的公式，我们引入 $F(0)=0$ (注意这不影响 $F(1)$ 和 $F(2)$ 的值)。此时，我们要求解的数列与标准斐波那契数列完全一致。递推关系可以一直延续到初始状态： $\begin{pmatrix} F(n) \\ F(n-1) \end{pmatrix} = M^{n-1} \begin{pmatrix} F(1) \\ F(0) \end{pmatrix} = M^{n-1} \begin{pmatrix} 1 \\ 0 \end{pmatrix}$

计算 $M^{n-1}$ 矩阵与向量 $\begin{pmatrix} 1 \\ 0 \end{pmatrix}$ 的乘积，会得到结果矩阵的第一列。其中，第一行的元素就是我们要求的 $F(n)$ 。这等价于求出 $M^{n-1}$ 矩阵，然后取其左上角的元素 [0][0]。

计算矩阵的幂次可以使用 快速幂 算法，其时间复杂度为 $\mathcal{O}(\log n)$ 。由于我们处理的是 2x2 矩阵，单次矩阵乘法是常数时间操作。

算法步骤：

定义 2x2 的转移矩阵 M。
编写一个矩阵乘法函数，计算两个 2x2 矩阵的乘积，并对结果取模。
编写一个矩阵快速幂函数，计算 M 的 n-1 次方。
对于输入的 n，计算 $M^{n-1}$ ，结果矩阵的 [0][0] 位置的元素即为 F(n)。

代码

cpp
java
python

#include <iostream>
#include <vector>

using namespace std;

long long MOD = 1000000007;

// 2x2 矩阵乘法
vector<vector<long long>> multiply(const vector<vector<long long>>& a, const vector<vector<long long>>& b) {
    vector<vector<long long>> c(2, vector<long long>(2));
    c[0][0] = (a[0][0] * b[0][0] + a[0][1] * b[1][0]) % MOD;
    c[0][1] = (a[0][0] * b[0][1] + a[0][1] * b[1][1]) % MOD;
    c[1][0] = (a[1][0] * b[0][0] + a[1][1] * b[1][0]) % MOD;
    c[1][1] = (a[1][0] * b[0][1] + a[1][1] * b[1][1]) % MOD;
    return c;
}

// 矩阵快速幂
vector<vector<long long>> matrix_pow(vector<vector<long long>> base, long long exp) {
    vector<vector<long long>> res = {{1, 0}, {0, 1}}; // 单位矩阵
    while (exp > 0) {
        if (exp % 2 == 1) res = multiply(res, base);
        base = multiply(base, base);
        exp /= 2;
    }
    return res;
}

int main() {
    long long n;
    cin >> n;

    if (n == 0) { // 虽然题目说是正整数，但以防万一
        cout << 0 << endl;
        return 0;
    }

    vector<vector<long long>> m = {{1, 1}, {1, 0}};
    vector<vector<long long>> res_matrix = matrix_pow(m, n - 1);

    cout << res_matrix[0][0] << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    static long MOD = 1000000007;

    // 2x2 矩阵乘法
    static long[][] multiply(long[][] a, long[][] b) {
        long[][] c = new long[2][2];
        c[0][0] = (a[0][0] * b[0][0] + a[0][1] * b[1][0]) % MOD;
        c[0][1] = (a[0][0] * b[0][1] + a[0][1] * b[1][1]) % MOD;
        c[1][0] = (a[1][0] * b[0][0] + a[1][1] * b[1][0]) % MOD;
        c[1][1] = (a[1][0] * b[0][1] + a[1][1] * b[1][1]) % MOD;
        return c;
    }

    // 矩阵快速幂
    static long[][] matrixPow(long[][] base, long exp) {
        long[][] res = {{1, 0}, {0, 1}}; // 单位矩阵
        while (exp > 0) {
            if (exp % 2 == 1) {
                res = multiply(res, base);
            }
            base = multiply(base, base);
            exp /= 2;
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();

        if (n == 0) {
            System.out.println(0);
            return;
        }
        
        long[][] m = {{1, 1}, {1, 0}};
        long[][] resMatrix = matrixPow(m, n - 1);
        
        System.out.println(resMatrix[0][0]);
    }
}

MOD = 1000000007

def multiply(a, b):
    c = [[0, 0], [0, 0]]
    c[0][0] = (a[0][0] * b[0][0] + a[0][1] * b[1][0]) % MOD
    c[0][1] = (a[0][0] * b[0][1] + a[0][1] * b[1][1]) % MOD
    c[1][0] = (a[1][0] * b[0][0] + a[1][1] * b[1][0]) % MOD
    c[1][1] = (a[1][0] * b[0][1] + a[1][1] * b[1][1]) % MOD
    return c

def matrix_pow(base, exp):
    res = [[1, 0], [0, 1]] # 单位矩阵
    while exp > 0:
        if exp % 2 == 1:
            res = multiply(res, base)
        base = multiply(base, base)
        exp //= 2
    return res

n = int(input())

if n == 0:
    print(0)
else:
    m = [[1, 1], [1, 0]]
    res_matrix = matrix_pow(m, n - 1)
    print(res_matrix[0][0])

算法及复杂度

算法：矩阵快速幂
时间复杂度： $\mathcal{O}(\log N)$ ，因为矩阵快速幂需要对 N 进行对数次矩阵乘法，而 2x2 矩阵乘法是常数时间操作。
空间复杂度： $\mathcal{O}(1)$ ，迭代实现的快速幂只需要常数个变量。