首页 > 试题广场 >

波斐契那数列

[编程题]波斐契那数列

热度指数：36 时间限制：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])

发表于今天 00:32:58 回复(0)

C++

huang_yp

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int Mod = 1e9 + 7;

vector<vector<ll>> mul(const vector<vector<ll>>& a,
const vector<vector<ll>>& b) {
    vector<vector<ll>> res(3, vector<ll>(3, 0));
    for(int i = 0; i < 3; i++) {
        for (int k = 0; k < 3; k++) {
            if (a[i][k])
                for (int j = 0; j < 3; j++) {
                    res[i][j] = (res[i][j] + a[i][k] * b[k][j]) % Mod;
                }
        }
    }
    return res;
}

vector<vector<ll>> mat_pow(vector<vector<ll>> a, ll k) {
    vector<vector<ll>> res = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
    while (k > 0) {
        if (k & 1) res = mul(res, a);
        a = mul(a, a);
        k >>= 1;
    }
    return res;
}

ll solve(ll n) {
    if (n == 1 || n == 2 || n == 3) return 1;
    vector<vector<ll>> mat = {
        {1, 0, 1},
        {1, 0, 0},
        {0, 1, 0}
    };
    auto m = mat_pow(mat, n - 3);
    return (m[0][0] * 1 + m[0][1] * 1 + m[0][2] * 1) % Mod;
}

int main() {
    int q;cin>>q;
    ll n;
    while(q--){
        cin>>n;
        cout<<solve(n)<<endl;
    }
    return 0;
}

发表于今天 10:29:59 回复(0)

提交观点

问题信息

难度：

2条回答 4收藏 34浏览

波斐契那数列

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

相关试题