首页 > 试题广场 >

波斐契那数列

[编程题]波斐契那数列

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

C++

7_by_wft_3

板子题。

对于数据范围，显然能想到矩阵快速幂

Code:

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
using ll = long long;
using vi = vector<ll>;
using vvi = vector<vi>;

vvi mul(const vvi& a, const vvi& b) 
{
    int n = a.size();
    vvi res(n, vi(n, 0));
    for (int i = 0; i < n; ++i) {
        for (int k = 0; k < n; ++k) {
            if (a[i][k] == 0) continue; 
            for (int j = 0; j < n; ++j) 
                res[i][j] = (res[i][j] + a[i][k] * b[k][j]) % mod;      
        }
    }
    return res;
}

vvi _pow(vvi a, ll power) {
    int n = a.size();
    vvi res(n, vi(n, 0));
    for (int i = 0; i < n; ++i) res[i][i] = 1;
    while (power > 0) {
        if (power & 1) res = mul(res, a);
        a = mul(a, a);
        power >>= 1;
    }
    return res;
}

ll solve(ll n) {
    if (n <= 3) return 1;
    vvi M={{1,0,1}, {1,0,0}, {0,1,0}}, M_pow = _pow(M, n - 3);

    // [a3, a2, a1]=[1, 1, 1]; a_n=M_pow[0][0]*a3+M_pow[0][1]*a2+M_pow[0][2]*a1

    ll a_n=(M_pow[0][0]+M_pow[0][1]+M_pow[0][2])%mod;
    return a_n;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T; cin >> T;
    while (T--) { ll n; cin >> n; cout << solve(n) << '\n'; }
}

发表于 2026-03-03 21:54:57 回复(0)

Lambda_L

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
#define int long long
#define vi vector<int>
#define vs vector<string>
#define vvi vector<vector<int>>
#define vb vector<bool>
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
#define ull unsigned long long
#define pb push_back
const int M = 2e5 + 7;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const double pi = acos(-1.0);
int inf = -1e18;
int dir[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
int n, m, k = 0, x, y, l, r;
string s;
int ksm(int a, int b, int p);
vvi mul(vvi &a,vvi &b)
{
    vvi c(3,vi(3,0));
    for(int i=0;i<3;i++)
    {
        for(int j=0;j<3;j++)
        {
            for(int k=0;k<3;k++)
            {
                c[i][j]=(c[i][j]+a[i][k]*b[k][j]%MOD+MOD)%MOD;
            }
        }
    }
    return c; 
}   
vvi pow(vvi &a,int p)
{
    vvi res(3,vi(3,0));
    for(int i=0;i<3;i++)res[i][i]=1;
    while(p>0)
    {
        if(p&1)
        {
            res=mul(res,a);
        }
        a=mul(a,a);
        p>>=1;
    }
    return res;
}

void solve()
{
    cin>>n;
    if(n<=3)
    {
        cout<<1<<endl;
        return;
    }
    vvi a={{1,0,1},
            {1,0,0},
            {0,1,0}};
    a=pow(a,n-3);
    cout<<((a[0][0]+a[0][1])%MOD+a[0][2])%MOD<<endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int qwq = 1;
    cin >> qwq;
    /*
    while (cin >> ws && cin.good())
    {
         solve();
    }
    */
    while (qwq--)
    {
        solve();
    }
    return 0;
}
int ksm(int a, int b, int p)
{
    int ans = 1;
    a %= p;
    while (b)
    {
        if (b & 1)
        {
            ans = ans * a % p;
        }
        a = a * a % p;
        b >>= 1;
    }
    return ans;
}

发表于 2026-02-26 21:42:50 回复(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;
}

发表于 2026-02-26 10:29:59 回复(0)

提交观点

问题信息

难度：

4条回答 12收藏 57浏览

波斐契那数列

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

相关试题