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

定义 , , ，求 是多少。
为了避免考虑整数溢出问题，我们求 的值，。

算法1

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

C++ 代码

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

算法2

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

C++ 代码

1
2
3
4
5
6
7
8
9
10
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

递推。
开一个大数组，记录每个数的值。用循环递推计算。
总共计算 个状态，所以时间复杂度是 。
但需要开一个长度是 的数组，内存将成为瓶颈，当 时，需要的内存是 。
分子中乘4是因为C++中 int 类型占4字节。

C++代码

1
2
3
4
5
6
7
8
9
10
11
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

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

C++代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
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秒内最多可以算到 级别，那当 更大时该怎么办呢？
可以先利用矩阵运算的性质将通项公式变成幂次形式，然后用平方倍增（快速幂）的方法求解第 项。

首先我们定义向量

边界：

然后我们可以找出矩阵：

则有：

所以：

由于矩阵具有结合律，所以我们可以先求出 ，然后再用 左乘，即可求出 ，向量 的第一个元素就是 。

时间复杂度分析：快速幂的时间复杂度是 ，所以算法5的时间复杂度也是 。

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#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;
}

思路

观察原式

移项可得

也就是

将斐波那契的前项都写成这种形式，得

累加所有等式，

左边正好是我们要求的答案

而右边，从到，都互相抵消掉了，

得到

也就是说，我们就只需要求出即可

这里给出三种求的算法

算法6 推式子 + 暴力

时间复杂度 O(n) 能过

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

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

结论

证明

结论对于成立

假设结论对于成立

则有

所以结论对于成立，证毕

那么根据结论，当 时，有

当 时，有

也就是说，我们可以通过递归求出 和 来得到

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

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

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

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

C++ 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#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 快速倍增法

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

时间复杂度

我们在做递归时，可以通过二元组的方式进行计算，并返回，将时间复杂度优化至

C ++ 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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;
}

来源