首页 > 试题广场 >

波斐契那数列

[编程题]波斐契那数列

热度指数：1046 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 定义数列 $\{a_x\}$ 满足

$a_x=\begin{cases}<br />1,& x\in\{1,2,3\};\\<br />a_{x-1}+a_{x-3},& x\geqq4.<br />\end{cases}$

$\hspace{15pt}$ 给定 $n$ ，请求出 $a_n\bmod\left(10^9+7\right)$ 的值。

输入描述:

 第一行输入整数 ，表示询问数量。 
 接下来  行，每行一个整数 。

输出描述:

 对于每个询问，在一行上输出  的值（取模 ）。

示例1

输入

输出

4
9
19

算法知识视频讲解

Python3

驴主

矩阵快速幂。

mod = int(1e9 + 7)


def mul(m1, m2):
    m2 = list(zip(*m2))
    return [
        [sum(x * y for x, y in zip(m1[i], m2[j])) % mod for j in range(3)]
        for i in range(3)
    ]


def pow(n):
    acc = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
    bof = [[0, 1, 0], [0, 0, 1], [1, 0, 1]]
    while n:
        if n & 1:
            acc = mul(acc, bof)
        bof = mul(bof, bof)
        n >>= 1
    return acc


t = int(input())
for _ in range(t):
    n = int(input())
    print(pow(n)[-1][0])

发表于 2026-02-26 00:32:58 回复(0)