首先定义斐波那契数列问题：

定义 $a_0=1$, $a_1=1$, $a_n=a_{n-1}+a_{n-2}$，求 $a_n$ 是多少。
为了避免考虑整数溢出问题，我们求 $a_n\mathrm{\%}p$ 的值，$p={10}^9+7$。

算法1

递归。
递归计算的节点个数是 $O(2^n)$ 的级别的，存在大量重复计算。
时间复杂度是 $O(2^n)$，一秒内大约能算到第三四十项。

C++ 代码

const int MOD = 1000000007;
int f(int n)
{
    if (n <= 1) return 1;
    return (f(n - 1) + f(n - 2)) % MOD;
}

---

算法2

记忆化搜索。
开一个大数组记录中间结果，如果一个状态被计算过，则直接查表，否则再递归计算。
总共有 $n$ 个状态，计算每个状态的复杂度是 $O(1)$，所以时间复杂度是 $O(n)$。
一秒内算 $n={10}^7$ 毫无压力，但由于是递归计算，递归层数太多会爆栈，大约只能算到 $n={10}^5$ 级别。

C++ 代码

const int N = 100000, MOD = 1000000007;
int a[N];
int f2(int n)
{
    if (a[n]) return a[n];
    if (n <= 1) return 1;
    a[n] = f2(n - 1) + f2(n - 2);
    a[n] %= MOD;
    return a[n];
}

---

算法3

递推。
开一个大数组，记录每个数的值。用循环递推计算。
总共计算 $n$ 个状态，所以时间复杂度是 $O(n)$。
但需要开一个长度是 $n$ 的数组，内存将成为瓶颈，当 $n={10}^8$ 时，需要的内存是 $\frac{4\ast {10}^8}{1024\times 1024}\approx 381MB$。
分子中乘4是因为C++中 int 类型占4字节。

C++代码

const int N = 100000000, MOD = 1000000007;
int f3(int n)
{
    a[0] = a[1] = 1;
    for (int i = 2; i <= n; i ++ )
    {
        a[i] = a[i - 1] + a[i - 2];
        a[i] %= MOD;
    }
    return a[n];
}

---

算法4

递归+滚动变量。
仔细观察我们会发现，递推时我们只需要记录前两项的值即可，没有必要记录所有值，所以我们可以用滚动变量递推。
时间复杂度还是 $O(n)$，但空间复杂度变成了 $O(1)$。

C++代码：

const int MOD = 1000000007;
int f4(int n)
{
    int x, y, z;
    x = y = 1;
    for (int i = 2; i <= n; i ++ )
    {
        z = (x + y) % MOD;
        x = y;
        y = z;
    }
    return z;
}

---

算法5

矩阵运算 + 快速幂。

快速幂算法的模板可以参考这里。
用算法4我们1秒内最多可以算到 ${10}^8$ 级别，那当 $n$ 更大时该怎么办呢？
可以先利用矩阵运算的性质将通项公式变成幂次形式，然后用平方倍增（快速幂）的方法求解第 $n$ 项。

首先我们定义向量

$$\begin{array}{}\text{(1)}& X_n=\begin{array}{cc}[a_n& a_{n-1}]\end{array},\mathrm{边}\mathrm{界}：X_1=\begin{array}{cc}[a_1& a_0]\end{array}\end{array}$$

然后我们可以找出矩阵：

$$\begin{array}{}\text{(2)}& A=\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]\end{array}$$

则有：

$$X_n=X_{n-1}\times A$$

所以：

$$X_n=X_1\times A^{n-1}$$

由于矩阵具有结合律，所以我们可以先求出 $A^{n-1}\mathrm{\%}P$，然后再用 $X_1$ 左乘，即可求出 $X_n$，向量 $X_n$ 的第一个元素就是 $a_n$。

时间复杂度分析：快速幂的时间复杂度是 $O(\log n)$，所以算法5的时间复杂度也是 $O(\log n)$。

C++代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <ctime>

using namespace std;

const int MOD = 1000000007;

void mul(int a[][2], int b[][2], int c[][2])
{
    int temp[][2] = {{0, 0}, {0, 0}};
    for (int i = 0; i < 2; i ++ )
        for (int j = 0; j < 2; j ++ )
            for (int k = 0; k < 2; k ++ )
            {
                long long x = temp[i][j] + (long long)a[i][k] * b[k][j];
                temp[i][j] = x % MOD;
            }
    for (int i = 0; i < 2; i ++ )
        for (int j = 0; j < 2; j ++ )
            c[i][j] = temp[i][j];
}


int f_final(long long n)
{
    int x[2] = {1, 1};

    int res[][2] = {{1, 0}, {0, 1}};
    int t[][2] = {{1, 1}, {1, 0}};
    long long k = n - 1;
    while (k)
    {
        if (k&1) mul(res, t, res);
        mul(t, t, t);
        k >>= 1;
    }

    int c[2] = {0, 0};
    for (int i = 0; i < 2; i ++ )
        for (int j = 0; j < 2; j ++ )
        {
            long long r = c[i] + (long long)x[j] * res[j][i];
            c[i] = r % MOD;
        }

    return c[0];
}


int main()
{
    long long n ;

    cin >> n;
    cout << f_final(n) << endl;

    return 0;
}

思路

$$\text{观察原式 }{f}_n=f_{n-1}+f_{n-2}$$$$\text{移项可得 }{f}_{n-2}=f_n-f_{n-1}$$$$\text{也就是 }{f}_n=f_{n+2}-f_{n+1}$$$$\text{将斐波那契的前}n\text{项都写成这种形式，得}$$$$\{\begin{array}{rl}{f}_1=& f_3-f_2\\ f_2=& f_4-f_3\\ f_3=& f_5-f_4\\ f_4=& f_6-f_5\\ & ⋮\\ f_n=& f_{n+2}-f_{n+1}\end{array}$$$$\text{累加所有等式，}$$$$\text{左边正好是我们要求的答案}$$$$\text{而右边，从}{f}_1\text{到}{f}_{n+1}，\mathrm{都}\mathrm{互}\mathrm{相}\mathrm{抵}\mathrm{消}\mathrm{掉}\mathrm{了}，$$$$\text{得到}$$$$f_1+f_2+\cdots +f_n=f_{n+2}-f_2=f_{n+2}-1$$$$\text{也就是说，我们就只需要求出 }{f}_{n+2}-1\text{ 即可}$$$$\text{这里给出三种求的算法}$$

算法6 推式子 + 暴力

时间复杂度 ~O(n)~ $O($能过$)$

空间复杂度 ~O(n)~ $O($超级大$)$

这里先给出结论，再给出证明过程

结论 $f_n=f_k{f}_{n-k+1}+f_{k-1}{f}_{n-k}(k\le n)$

证明

$\because f_n=f_{n-1}+f_{n-2}=f_2{f}_{n-2+1}+f_1{f}_{n-2}$

$\therefore \mathrm{结}\mathrm{论}\mathrm{对}\mathrm{于}k=1\mathrm{成}\mathrm{立}$

$\mathrm{假}\mathrm{设}\mathrm{结}\mathrm{论}\mathrm{对}\mathrm{于}k=i\mathrm{成}\mathrm{立}$

$\mathrm{则}\mathrm{有}{f}_n=f_i{f}_{n-i+1}+f_{i-1}{f}_{n-i}$

$\Rightarrow =f_i(f_{n-i}+f_{n-i-1})+f_{i-1}{f}_{n-i}$

$\Rightarrow =f_i{f}_{n-i}+f_i{f}_{n-i-1}+f_{i-1}{f}_{n-i}$

$\Rightarrow =(f_i+f_{i-1})f_{n-i}+f_i{f}_{n-i-1}$

$\Rightarrow =f_{i+1}{f}_{n-i}+f_i{f}_{n-i-1}$

$\mathrm{所}\mathrm{以}\mathrm{结}\mathrm{论}\mathrm{对}\mathrm{于}k=i+1\mathrm{成}\mathrm{立}，\mathrm{证}\mathrm{毕}$

那么根据结论，当 $n=2k$ 时，有
$f_{2k}=f_k{f}_{k+1}+f_{k-1}{f}_k=f_k(f_{k+1}+f_{k-1})=f_k(2f_{k+1}-f_k)$

当 $n=2k+1$ 时，有
$f_{2k+1}=f_k{f}_k+f_{k+1}{f}_{k+1}=f_k^2+f_{k+1}^2$

也就是说，我们可以通过递归求出 $f_{\lfloor \frac{k}{2}\rfloor }$ 和 $f_{\lfloor \frac{k}{2}\rfloor +1}$ 来得到 $f_k$

直接这么求，时间复杂度还是 $O(n)$，和递推相比，并没有任何优化

但是这个做法的优点，是可以快速将我们要求的 $f_n$ 的 $n$ 缩小到一个很小的范围内

利用这一点，我们可以预处理出 $f$ 的前 $k$ 项（具体 $k$ 的值根据题目而定）

如果递归到了 $k$ 以内，直接返回我们预处理好的值

C++ 代码

#include <iostream>

using namespace std;

typedef long long ll;
const int k = 1e7 + 5; // 这里取 k = 1e7 + 5

int n, m;
int f[k];

// 递归求出 f[x] 的值
ll calc(int x)
{
    if (x < k) return f[x]; // 如果 x 在我们预处理的 k 之内，则直接返回我们预处理出的值
    ll t1 = calc(x / 2 + 1), t2 = calc(x / 2); // 递归求出 f[x / 2 + 1] 和 f[x / 2]
    if (x & 1) return (t1 * t1 + t2 * t2) % m; // 按照上述等式，返回 x 是奇数时的结果
    return t2 * (t1 * 2 - t2 % m + m) % m; // 返回 x 是偶数时的结果，注意这里求的是 % m 的正余数，要在括号内先加上 m，以保证结果为正数
}

int main()
{
    scanf("%d %d", &n, &m);

    f[1] = f[2] = 1; // 递推求出 f[0 ~ k - 1] 的值
    for (int i = 3; i < k; i ++ )
        f[i] = (f[i - 1] + f[i - 2]) % m;

    printf("%lld\n", calc(n + 2) - 1); // 输出结果

    return 0;
}

算法7 快速倍增法

这里感谢@洛零巨佬给出该方法

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

我们在做递归时，可以通过二元组的方式进行计算，并返回$(f_n,f_{n+1})$，将时间复杂度优化至 $O(\log n)$

C ++ 代码

#include <cstdio>
#include <utility>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

int n, m;

// 递归求出二元组 {f[x], f[x + 1]}
pll calc(int x)
{
    if (!x) return make_pair(0, 1);         // 如果 x 为 0，那么返回 (0, 1)
    pll u = calc(x >> 1);                   // 递归求出二元组 (f[x / 2], f[x / 2 + 1])
    ll t1 = u.first, t2 = u.second;         // 分别取出 f[x / 2] 和 f[x / 2 + 1]
    ll f2 = t1 * (2 * t2 - t1 % m + m) % m; // 求出 (f[x], f[x + 1]) 中，x 为奇数的元素的值
    ll f1 = (t1 * t1 + t2 * t2) % m;        // 求出 (f[x], f[x + 1]) 中，x 为偶数的元素的值
    if (!(x & 1)) return make_pair(f2, f1); // 如果 x 是偶数，则 f[x] = f2，直接返回 (f2, f1) 即可
    return make_pair(f1, (f1 + f2) % m);    // 否则说明 x 是奇数，则 f[x] = f1，需要求下 f[x + 1] 再返回
}

int main()
{
    scanf("%d %d", &n, &m);

    printf("%lld\n", calc(n + 2).first - 1); // 输出结果

    return 0;
}

---

来源

• 求解斐波那契数列的若干方法 - AcWing

• AcWing 1303. 斐波那契前 n 项和——另一个更巧妙的解法 - AcWing