题解：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.

，很容易想到一个暴力代码，如下：

CPP

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$ 给台阶则走到最高的台阶的方案可以分成两类：

先走上第 $n$ 级台阶（方案数为 $G_n$ ）再走上第 $n + m$ 级台阶（方案数为 $G_m$ ），根据乘法原理可得此类方案数为 $G_n G_m$ 。

先走上第 $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

CPP

#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;
}

题解：P1962 斐波那契数列

文章操作

前言

题目简述

题目思路

AC code

相关推荐

评论

题解：P1962 斐波那契数列