题解：P1962 斐波那契数列

· · 题解

题目链接

前言

此题解给不会矩阵和想有易懂数学证明方法的人。

题目简述

求斐波拉契数列第 n 项。

题目思路

首先根据斐波拉契数列的递推式：F_n = \left\{\begin{aligned} 1 \space (n \le 2) \\ F_{n-1}+F_{n-2} \space (n\ge 3) \end{aligned}\right.，很容易想到一个暴力代码，如下：

int n, a = 1, b = 1;
cin >> n;
for (int i = 3; i <= n; i ++ ) {
    int t = a;
    a = a + b;
    b = t;
}
cout << a << '\n';

时间复杂度 \Theta (n) 显然会 TLE。于是我们就要优化递推式。

结论：F_{n + m - 1} = F_n F_m + F_{n - 1} F_{m - 1} \space (n + m - 1 \ge 1)。 证明：

考虑一个数列 G，其第 n 项表示有 n 级台阶（每步只能上 1 级或 2 级）的方案数。显然 G_0 = G_1 = 1。第 n 级台阶只能从第 n - 1 级或第 n - 2 走来。根据加法原理可得 G_n = G_{n - 1} + G_{n - 2}。对比斐波拉契递推式可得 G_{n - 1} = F_n。考虑现在有 n + m 给台阶则走到最高的台阶的方案可以分成两类：

  1. 先走上第 n 级台阶（方案数为 G_n）再走上第 n + m 级台阶（方案数为 G_m），根据乘法原理可得此类方案数为 G_n G_m。
  2. 先走上第 n - 1 级台阶（方案数为 G_{n - 1}）再直接走上第 n + 2 级台阶（方案数为 1），最后走上第 n + m 级台阶（方案数为 G_{m - 1}），根据乘法原理可得此类方案数为 G_{n - 1} G_{m - 1}。 根据加法原理可得 G_{n + m} = G_n G_m + G_{n - 1} G_{m - 1} 即 F_{n + m - 1} = F_n F_m + F_{n - 1} F_{m - 1} \space (n + m - 1 \ge 1)。

现在我们要计算 F_x 我们可以考虑把 x 拆分成 \left \lfloor \frac{x}{2} \right \rfloor + 1 和 x - \left \lfloor \frac{x}{2} \right \rfloor。根据公式，F_x = F_{\left \lfloor \frac{x}{2} \right \rfloor + 1} F_{x - \left \lfloor \frac{x}{2} \right \rfloor} + F_{\left \lfloor \frac{x}{2} \right \rfloor} F_{x - \left \lfloor \frac{x}{2} \right \rfloor - 1}。这样我们就可以递归求解，记忆化优化时间复杂度 \Theta (\log n)。

AC code

#include <bits/stdc++.h>

#define int long long

using namespace std;
const int mod = 1e9 + 7;

int n;
unordered_map<int, int> fie = {{1, 1}, {2, 1}};

int f(int x) {
    if (fie[x] != 0)  return fie[x];
    int m = x >> 1;
    return fie[x] = (f(m + 1) * f(x - m) % mod + f(m) * f(x - m - 1) % mod) % mod;
}

signed main(){
    ios::sync_with_stdio(false);    cin.tie(nullptr);
    cin >> n;
    cout << f(n) << '\n';
    return 0;
}