题解 | #波斐契那数列#

题目链接

波斐契那数列

题目描述

定义数列 $a_x$ 满足： $a_x = \begin{cases} 1, & x \in \{1,2,3\} \\ a_{x-1}+a_{x-3}, & x \ge 4 \end{cases}$

给定 $n$ ，请求出 $a_n$ 的值。由于结果可能很大，请对 $10^9+7$ 取模。

解题思路

这是一个典型的线性递推关系求解问题。由于 $n$ 的范围可以达到 $10^{18}$ ，使用简单的 $O(n)$ 递推或递归会超时。对于这类问题，标准的高效解法是矩阵快速幂 (Matrix Exponentiation)。

算法步骤

建立状态向量: 递推关系 $a_n = a_{n-1} + a_{n-3}$ 依赖于前三项中的两项。为了能够从第 $n-1$ 步的状态推导出第 $n$ 步的状态，我们需要维护一个包含足够历史信息的状态向量。选择一个 $3 \times 1$ 的向量是合适的，因为它包含了计算 $a_n$ 所需的所有项：
$\begin{bmatrix} a_{n-1} \\ a_{n-2} \\ a_{n-3} \end{bmatrix}$
构建转移矩阵: 我们的目标是找到一个 $3 \times 3$ 的转移矩阵 $T$ ，使得：

$\begin{bmatrix} a_{n} \\ a_{n-1} \\ a_{n-2} \end{bmatrix} = T \cdot \begin{bmatrix} a_{n-1} \\ a_{n-2} \\ a_{n-3} \end{bmatrix}$

根据递推关系填充矩阵 $T$ ：
- 第一行（计算 $a_n$ ）： $a_n = 1 \cdot a_{n-1} + 0 \cdot a_{n-2} + 1 \cdot a_{n-3}$ 。所以第一行为 $[1, 0, 1]$ 。
- 第二行（计算 $a_{n-1}$ ）： $a_{n-1} = 1 \cdot a_{n-1} + 0 \cdot a_{n-2} + 0 \cdot a_{n-3}$ 。所以第二行为 $[1, 0, 0]$ 。
- 第三行（计算 $a_{n-2}$ ）： $a_{n-2} = 0 \cdot a_{n-1} + 1 \cdot a_{n-2} + 0 \cdot a_{n-3}$ 。所以第三行为 $[0, 1, 0]$ 。
因此，转移矩阵 $T$ 为：

$T = \begin{bmatrix} 1 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix}$
应用矩阵快速幂: 通过重复应用上述关系，我们可以从一个已知的初始状态（例如 $n=3$ 时的状态）推广到任意的 $n$ ：
$\begin{bmatrix} a_{n} \\ a_{n-1} \\ a_{n-2} \end{bmatrix} = T^{n-3} \cdot \begin{bmatrix} a_{3} \\ a_{2} \\ a_{1} \end{bmatrix}$
这个公式对于 $n \ge 4$ 成立。根据题意， $a_1=a_2=a_3=1$ ，所以我们的初始状态向量为 $[1, 1, 1]^T$ 。
求解:
- 对于给定的 $n$ ，如果 $n \le 3$ ，答案直接为 1。
- 如果 $n > 3$ ，我们使用矩阵快速幂算法计算出 $T^{n-3}$ ，记为 $T'$ 。
- 最终的 $a_n$ 是 $T'$ 与初始向量相乘后得到的向量的第一个元素。即： $a_n = (T'_{00} \cdot a_3 + T'_{01} \cdot a_2 + T'_{02} \cdot a_1) \pmod{MOD}$ 由于 $a_1=a_2=a_3=1$ ，这简化为： $a_n = (T'_{00} + T'_{01} + T'_{02}) \pmod{MOD}$

这样，我们就将问题转化为了一个 $3 \times 3$ 矩阵的快速幂计算，可以在 $O(\log n)$ 的时间内解决单次查询。

代码

cpp
java
python

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 1e9 + 7;

// 定义矩阵类型
using Matrix = vector<vector<long long>>;

// 矩阵乘法 (3x3)
Matrix multiply(const Matrix& a, const Matrix& b) {
    Matrix c(3, vector<long long>(3, 0));
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            for (int k = 0; k < 3; ++k) {
                long long product = a[i][k] * b[k][j];
                c[i][j] = (c[i][j] + product % MOD + MOD) % MOD;
            }
        }
    }
    return c;
}

// 矩阵快速幂 (3x3)
Matrix matrix_pow(Matrix base, long long exp) {
    Matrix res(3, vector<long long>(3, 0));
    // 初始化为单位矩阵
    for (int i = 0; i < 3; ++i) {
        res[i][i] = 1;
    }

    while (exp > 0) {
        if (exp % 2 == 1) {
            res = multiply(res, base);
        }
        base = multiply(base, base);
        exp /= 2;
    }
    return res;
}

void solve() {
    long long n;
    cin >> n;
    if (n <= 3) {
        cout << 1 << "\n";
        return;
    }

    Matrix T = {
        {1, 0, 1},
        {1, 0, 0},
        {0, 1, 0}
    };

    Matrix T_pow = matrix_pow(T, n - 3);
    
    // a_n = T_pow[0][0]*a3 + T_pow[0][1]*a2 + T_pow[0][2]*a1
    // since a1=a2=a3=1, a_n is the sum of the first row
    long long ans = (T_pow[0][0] + T_pow[0][1] + T_pow[0][2]) % MOD;
    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

import java.util.Scanner;

public class Main {
    static final int MOD = 1_000_000_007;

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

    // 矩阵快速幂 (3x3)
    public static long[][] matrixPow(long[][] base, long exp) {
        long[][] res = new long[3][3];
        // 初始化为单位矩阵
        for (int i = 0; i < 3; i++) {
            res[i][i] = 1;
        }

        while (exp > 0) {
            if (exp % 2 == 1) {
                res = multiply(res, base);
            }
            base = multiply(base, base);
            exp /= 2;
        }
        return res;
    }
    
    public static void solve(Scanner sc) {
        long n = sc.nextLong();

        if (n <= 3) {
            System.out.println(1);
            return;
        }

        long[][] T = {
            {1, 0, 1},
            {1, 0, 0},
            {0, 1, 0}
        };

        long[][] T_pow = matrixPow(T, n - 3);
        
        long ans = (T_pow[0][0] + T_pow[0][1] + T_pow[0][2]) % MOD;
        System.out.println(ans);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            solve(sc);
        }
    }
}

import sys

MOD = 10**9 + 7

def multiply(a, b):
    c = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
    for i in range(3):
        for j in range(3):
            for k in range(3):
                c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD
    return c

def matrix_pow(base, exp):
    res = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
    for i in range(3):
        res[i][i] = 1

    while exp > 0:
        if exp % 2 == 1:
            res = multiply(res, base)
        base = multiply(base, base)
        exp //= 2
    return res

def solve():
    n = int(sys.stdin.readline())
    if n <= 3:
        sys.stdout.write("1\n")
        return

    T = [
        [1, 0, 1],
        [1, 0, 0],
        [0, 1, 0]
    ]

    T_pow = matrix_pow(T, n - 3)
    
    # a_n = T_pow[0][0]*a3 + T_pow[0][1]*a2 + T_pow[0][2]*a1
    # since a1=a2=a3=1, a_n is the sum of the first row
    ans = (T_pow[0][0] + T_pow[0][1] + T_pow[0][2]) % MOD
    sys.stdout.write(str(ans) + '\n')

def main():
    try:
        t_str = sys.stdin.readline()
        if not t_str: return
        t = int(t_str)
        for _ in range(t):
            solve()
    except (IOError, ValueError):
        return

main()

算法及复杂度

算法：矩阵快速幂 (Matrix Exponentiation)
时间复杂度： $O(T \cdot N^3 \cdot \log n)$ ，其中 $T$ 是询问次数， $N=3$ 是矩阵维度， $n$ 是数列的项数。由于 $N$ 是一个很小的常数，所以单次查询的复杂度为 $O(\log n)$ 。
空间复杂度： $O(N^2)$ ，用于存储矩阵。由于 $N=3$ ，空间复杂度为 $O(1)$ 。