关于使用 递归来解决斐波拉契问题

每步取余 有效防止一些奇奇怪怪的小错误

其中 第一个和第二个数据特判就行了 不用整太麻烦 这个题简单就直接上代码把

Code:

#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long

using namespace std;

const int Num = 1e9 + 7;
int n;
int a = 1 , b = 1;
void fi(int u)
{

    int temp = (a + b) % Num;
    a = b , b = temp;

    if (u == n)
    {
        cout << temp << endl;
        return ;
    }

    fi(u + 1);
}
signed main()
{
    cin >> n;

    if (n == 1 || n == 2)
    {
        cout << "1" << endl;
        return 0;
    }
    else 
        fi(3);
    
    return 0;
}

#include<iostream>

using namespace std;

const int N = 1000010;
const int mod = 1e9 + 7;
int a[N];

int main()
{
    int n;

    cin >> n;
    a[1] = 1, a[2] = 1;
    for (int i = 3; i <= n; ++i)
    {
        a[i] = (a[i - 1] + a[i - 2]) % mod;
    }
    cout << a[n] << endl;

    return 0;
}

P0068 斐波那契II

给定一个整数 n，要求计算斐波那契数列的第 n 项对 $10^9+7$ 取模的结果。

斐波那契序列 $F_1, F_2,...$ 定义为

$$     F_1 = 1, F_2 = 1, F_n = F_{n-2} + F_{n-1} \  \ (n\ge3). $$

注意到斐波那契数列中存在线性关系

$$ \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} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{{n-1}} \begin{pmatrix} 1 \\ 1 \end{pmatrix} $$

可以看出若记 $A = \begin{pmatrix}1 & 1 \\ 1 & 0\end{pmatrix}$ 则求 $F_n$ 就转换为对矩阵 $A$ 求幂。

代码

struct M {
    i64 a, b, c, d;
    M(i64 a=1, i64 b=1, i64 c=1, i64 d=0): a(a), b(b), c(c), d(d) {}
};

M m_mul(const M &x, const M &y) {
    return M(
        (x.a * y.a + x.b * y.c) % MOD,
        (x.a * y.b + x.b * y.d) % MOD,
        (x.c * y.a + x.d * y.c) % MOD,
        (x.c * y.b + x.d * y.d) % MOD
    );
}

M m_pow(M base, int n) {
    M res(1, 0, 0, 1);
    while(n) {
        if (n & 1) res = m_mul(res, base);
        base = m_mul(base, base);
        n >>= 1;
    }
    return res;
}

时间复杂度 $\cal O(\log n)$