题目描述{:target=”_blank”}

这里的做法，和这个做法{:target=”_blank”}的时间复杂度是相同的，但常数更小

思路

$$\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{项都写成这种形式，得}$$

$$\left\{ \begin{aligned} f _ 1 = &\ f _ 3 - f _ 2 \\ f _ 2 = &\ f _ 4 - f _ 3 \\ f _ 3 = &\ f _ 5 - f _ 4 \\ f _ 4 = &\ f _ 6 - f _ 5 \\ &\ \ \vdots \\ f _ n = &\ f _ {n + 2} - f _ {n + 1} \\ \end{aligned} \right.$$

$$\text{累加所有等式，}$$

$$\text{左边正好是我们要求的答案}$$

$$\text{而右边，从}f _ 1\text{到}f _ {n + 1}{，都互相抵消掉了，}$$

$$\text{得到}$$

$$f _ 1 + f _ 2 + \cdots + f _ n = f _ {n + 2} - f _ 2 = f _ {n + 2} - 1$$

$$\text{也就是说，我们就只需要求出 }f _ {n + 2} - 1\text{ 即可}$$

$$\text{这里给出三种求的算法}$$

算法1$\ \ $矩阵快速幂

这里不再做过多赘述，关于矩阵快速幂的方法可以看下面的参考文献

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

参考文献1$\ \ $求斐波那契数列若干方法{:target=”_blank”}

参考文献2$\ \ $如何通过递推式构造矩阵{:target=”_blank”}

C++ 代码

#include <iostream>

using namespace std;

typedef long long ll;

int n, m;
ll A[2][2] = {      // 用于快速幂的矩阵
    {1, 1},
    {1, 0}
};
ll res[2] = {1, 0}; // 用于存答案的矩阵（转置）

// 计算列矩阵 A 乘方阵 B 的乘积，并存储在 A 中
void _multi(ll A[], ll B[][2])
{
    ll ans[2] = {0};
    for (int i = 0; i < 2; i ++ )
        for (int j = 0; j < 2; j ++ )
            ans[i] += A[j] * B[i][j] % m;
    for (int i = 0; i < 2; i ++ )
        A[i] = ans[i] % m;
}

// 计算方阵 A 乘方阵 B 的乘积，并存储在 A 中
void multi(ll A[][2], ll B[][2])
{
    ll ans[2][2] = {0};
    for (int i = 0; i < 2; i ++ )
        for (int j = 0; j < 2; j ++ )
            for (int k = 0; k < 2; k ++ )
                ans[i][j] += A[i][k] * B[k][j] % m;
    for (int i = 0; i < 2; i ++ )
        for (int j = 0; j < 2; j ++ )
            A[i][j] = ans[i][j] % m;
}

int main()
{
    scanf("%d %d", &n, &m);
    n += 2; // 求 f[n + 2] 的结果

    while (n) // 矩阵快速幂板子
    {
        if (n & 1) _multi(res, A);
        multi(A, A);
        n >>= 1;
    }

    printf("%lld\n", res[1] - 1); // 最后 res[1] 即为 f[n + 2] 的结果

    return 0;
}

算法2$\ \ $推式子 + 暴力

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

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

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

结论$\ \ f _ n = f _ {k} f _ {n - k + 1} + f _ {k - 1} f _ {n - k}\ \ (k \leq n)$

证明

$\because f _ n = f _ {n - 1} + f _ {n - 2} = f _ 2 f _ {n - 2 + 1} + f _ 1 f _ {n - 2}$

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

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

$则有 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}$

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

那么根据结论，当 $n = 2k$ 时，有
$f _ {2k} = f _ {k} f _ {k + 1} + f _ {k - 1} f _ {k} = f _ {k} (f _ {k + 1} + f _ {k - 1}) = f _ {k} (2 f _ {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;
}

算法3$\ \ $快速倍增法

这里感谢@洛零{:target=”_blank”}巨佬给出该方法

时间复杂度 $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;
}