从斐波那契到Pell数列：数学递推问题的通用解法与优化策略

从斐波那契到Pell数列：数学递推问题的通用解法与优化策略

如果你接触过编程竞赛或者算法学习，那么“斐波那契数列”这个名字一定不会陌生。从经典的兔子繁殖问题，到黄金分割的数学之美，再到动态规划的入门案例，斐波那契几乎成了算法世界的“Hello World”。但算法世界远不止于此。当你熟练掌握了斐波那契的几种解法后，有没有想过，类似的递推问题是否有一套通用的“解题模板”？今天，我们就以另一个在信息学奥赛（如NOI、OpenJudge）中频繁出现的经典数列——Pell数列——作为切入点，深入探讨数学递推问题的通用解法框架与核心优化策略。这不仅仅是解一道题，更是掌握一类问题的思考方式。

Pell数列的定义很简单：a₁ = 1, a₂ = 2, aₙ = 2*aₙ₋₁ + aₙ₋₂ (n>2)。它与斐波那契数列（F₁=1, F₂=1, Fₙ=Fₙ₋₁+Fₙ₋₂）在形式上同属二阶线性齐次递推，只是系数从(1,1)变成了(2,1)。这微小的变化背后，却蕴含着完全相同的算法内核与截然不同的优化挑战。本文将带你跳出单一题目的局限，构建一个从暴力递归到高效迭代，再到矩阵快速幂乃至通项公式的完整方法论体系。无论你是正在备战ybt（一本通）题单的选手，还是希望深化算法理解的开发者，这篇文章都将为你提供一套清晰、可复用的实战指南。

1. 理解本质：从具体数列到通用递推模型

在动手写代码之前，我们必须先跳出“Pell数列”或“斐波那契数列”的具体形式，看到它们背后统一的数学模型。这是选择正确解法的前提。

1.1 线性递推式的标准形式

无论是斐波那契还是Pell，都可以归结为以下形式的二阶线性齐次递推关系：

F(n) = p * F(n-1) + q * F(n-2)， 其中 n > 2

• 对于斐波那契数列：p = 1,q = 1
• 对于Pell数列：p = 2,q = 1

这个模型有两个关键特征：

1. 线性：递推式中，F(n)是F(n-1)和F(n-2)的线性组合（即只涉及常数乘法和加法）。
2. 齐次：递推式右边没有额外的常数项。

理解这一点至关重要，因为许多高级优化算法（如矩阵快速幂）正是建立在这个标准形式之上的。此外，初始条件F(1)和F(2)的值，与系数p、q一起，共同决定了整个数列的唯一性。

1.2 问题场景与约束分析

在实际的算法题目中（如OpenJudge NOI 2.2/2.3 1788题），除了递推关系，我们还会面临具体的约束条件，这直接决定了我们能否使用某种解法以及如何进行优化。

以典型的Pell数列题目为例，常见的约束包括：

• 多组询问：输入的第一行是一个整数n，表示有n组测试数据，随后n行每行一个整数k，要求输出Pell数列第k项对32767取模的结果。
• 数据范围：k可能非常大（例如高达10^6甚至更大）。
• 取模运算：结果需要对一个固定的数（如32767）取模，这通常是为了防止整数溢出，同时也暗示了结果可能存在周期性等性质。

注意：取模运算(a+b)%M等价于(a%M + b%M)%M，(a*b)%M等价于((a%M)*(b%M))%M。在递推计算中，我们可以每一步都取模，以保证中间结果不会溢出，并且最终结果正确。这是处理大数递推的常用技巧。

面对这些约束，一个天真的递归实现会立刻崩溃。我们需要系统地评估不同解法的优劣。

2. 解法演进：从直观到高效的四层突破

解决递推问题，就像升级打怪，有不同的“段位”。我们按照时间复杂度和思维深度，将其分为四个层次。

2.1 第一层：暴力递归及其根本缺陷

最直观的想法是直接根据定义写出递归函数。对于Pell数列，代码看起来非常简洁：

def pell_naive(k): if k == 1: return 1 if k == 2: return 2 return (2 * pell_naive(k-1) + pell_naive(k-2)) % 32767

为什么这种方法行不通？因为它存在大量的重复计算。以计算pell_naive(5)为例，其递归树如下：

pell(5) ├── 2*pell(4) + pell(3) │ ├── pell(4) -> 2*pell(3) + pell(2) │ │ ├── pell(3) -> 2*pell(2) + pell(1) # 这里计算了一次pell(3) │ │ └── pell(2) │ └── pell(3) -> 2*pell(2) + pell(1) # 这里又计算了一次pell(3)！ └── pell(3) -> 2*pell(2) + pell(1) # 这里第三次计算pell(3)！

pell(3)被计算了3次。随着k增大，重复计算的数量呈指数级增长，时间复杂度约为O(2^k)。当k=30时，计算量已经超过10亿次，完全不可接受。这是算法学习中关于递归效率最经典的负面教材。

2.2 第二层：记忆化递归——用空间换时间

既然问题是重复计算，那么最直接的优化就是“记住”已经算过的结果，避免重复劳动。这就是记忆化搜索（Memoization）的核心思想。

我们引入一个数组（或字典）memo，memo[i]用于存储pell(i)的结果。在递归函数中，先检查memo[k]是否已经计算过，如果是，直接返回；否则才进行计算，并将结果存入memo。

MAX_K = 1000000 # 根据题目数据范围预设 MOD = 32767 memo = [0] * (MAX_K + 1) # 初始化记忆数组 memo[1], memo[2] = 1, 2 # 设定初始值 def pell_memo(k): if memo[k] != 0: # 已经计算过，直接返回 return memo[k] # 否则，递归计算并存储 memo[k] = (2 * pell_memo(k-1) + pell_memo(k-2)) % MOD return memo[k]

复杂度分析：

• 时间复杂度：每个pell(i)只会被计算一次，之后都是O(1)时间的查表。因此总时间复杂度为O(n + max_k)，其中n是询问次数，max_k是所有询问中最大的k。预处理后，每次询问是O(1)。
• 空间复杂度：需要O(max_k)的数组来存储结果。

记忆化递归是解决重叠子问题的一个优美方案，它保持了递归的思维直观性，又拥有了接近迭代的效率。在ybt 1189这类题目中，这通常是能够AC（通过）的解法之一。

2.3 第三层：迭代与动态规划——效率的极致

递归调用本身有函数调用的开销。对于线性递推，我们完全可以摆脱递归，使用循环迭代地计算出所有项。这本质上就是最简单的动态规划（DP）。

思路：既然我们知道了a[1]和a[2]，那么就可以顺序地计算出a[3],a[4], ...直到a[k]。

实现方式有两种：

方式一：使用数组存储所有项（预处理）这是应对多组询问场景的最高效方法。我们一次性计算出前max_k项（或题目允许的最大范围），存入数组。之后对于任何询问，直接输出数组对应下标的值即可。

#include <iostream> using namespace std; const int MOD = 32767; const int MAX_N = 1000000; // 假设最大k为100万 int pell[MAX_N + 1]; // 数组从1开始索引 void precompute() { pell[1] = 1; pell[2] = 2; for (int i = 3; i <= MAX_N; ++i) { pell[i] = (2 * pell[i-1] + pell[i-2]) % MOD; } } int main() { precompute(); // 程序开始先预处理 int n, k; cin >> n; for (int i = 0; i < n; ++i) { cin >> k; cout << pell[k] << endl; // O(1)时间回答 } return 0; }

方式二：滚动变量（空间优化）如果只需要求某一项，或者内存极其受限，我们注意到计算a[i]时，只需要a[i-1]和a[i-2]。我们可以只用两个（或三个）变量来“滚动”更新，将空间复杂度从O(n)降至O(1)。

def pell_iterative(k): if k == 1: return 1 if k == 2: return 2 a, b = 1, 2 # a代表a_{i-2}, b代表a_{i-1} for _ in range(3, k + 1): # 计算下一项: a_i = 2*b + a next_val = (2 * b + a) % 32767 # 滚动更新：a变成原来的b，b变成新计算的next_val a, b = b, next_val return b

迭代法是解决此类问题的标准答案，它代码简洁，效率极高（时间复杂度O(k)，空间O(1)或O(n)），是竞赛和工程中的首选。

2.4 第四层：矩阵快速幂——应对超大规模的降维打击

当k变得极其巨大（比如10^18）时，即使是O(k)的迭代法也无法胜任。这时，我们需要O(log k)的算法。秘密武器就是矩阵快速幂。

我们观察Pell数列的递推式：

a_n = 2*a_{n-1} + 1*a_{n-2} a_{n-1} = 1*a_{n-1} + 0*a_{n-2}

这可以改写为矩阵乘法的形式：

[ a_n ] = [ 2 1 ] * [ a_{n-1} ] [ a_{n-1} ] [ 1 0 ] [ a_{n-2} ]

令F(n) = [a_n, a_{n-1}]^T，M = [[2,1],[1,0]]，则有：

F(n) = M * F(n-1)

递归下去，可以得到：

F(n) = M^(n-2) * F(2)， 其中 F(2) = [a_2, a_1]^T = [2, 1]^T

于是，问题转化为求矩阵M的(n-2)次幂。而矩阵的幂运算可以通过快速幂算法在O(log n)时间内完成。

MOD = 32767 def matmul(A, B): """2x2矩阵乘法，结果对MOD取模""" return [ [(A[0][0]*B[0][0] + A[0][1]*B[1][0]) % MOD, (A[0][0]*B[0][1] + A[0][1]*B[1][1]) % MOD], [(A[1][0]*B[0][0] + A[1][1]*B[1][0]) % MOD, (A[1][0]*B[0][1] + A[1][1]*B[1][1]) % MOD] ] def mat_pow(M, power): """矩阵快速幂""" # 单位矩阵 result = [[1, 0], [0, 1]] base = M while power > 0: if power & 1: # 如果当前二进制位为1 result = matmul(result, base) base = matmul(base, base) # 基数平方 power >>= 1 # 幂次右移一位 return result def pell_matrix(k): if k == 1: return 1 if k == 2: return 2 M = [[2, 1], [1, 0]] # 计算 M^(k-2) M_pow = mat_pow(M, k-2) # F(k) = M^(k-2) * F(2) # F(2) = [a2, a1]^T = [2, 1]^T a_k = (M_pow[0][0] * 2 + M_pow[0][1] * 1) % MOD return a_k

这种方法将时间复杂度从O(k)降至O(log k)，能够轻松处理k为几十甚至几百位的大整数情况，是解决超大项递推问题的终极武器。

3. 策略选择：如何根据场景匹配合适的解法？

掌握了各种武器，关键在于如何选用。下面这个决策表可以帮助你快速做出选择：

在实际的信息学奥赛题目中，像ybt 1189或OpenJudge NOI 2.2 1788，通常k的最大值在10^6量级，并且有n组（n也可能很大）询问。因此，解法3（预处理数组的迭代法）是最稳妥、最标准的选择。它完美平衡了效率与实现难度。

4. 超越Pell：通用递推问题的扩展与实战

Pell数列只是一个引子。掌握了这套方法论，你可以解决一大类线性递推问题。

4.1 扩展到更高阶递推

斐波那契和Pell是二阶递推。对于三阶递推，例如a_n = p*a_{n-1} + q*a_{n-2} + r*a_{n-3}，我们依然可以构建矩阵：

[ a_n ] = [ p q r ] [ a_{n-1} ] [ a_{n-1} ] [ 1 0 0 ] * [ a_{n-2} ] [ a_{n-2} ] [ 0 1 0 ] [ a_{n-3} ]

矩阵的维度变为k x k（k为递推阶数）。快速幂算法的复杂度变为O(k^3 log n)，但对于固定的、较小的k，这仍然是O(log n)的。

4.2 非齐次递推与带系数的递推

有时递推式可能不是齐次的，比如a_n = 2*a_{n-1} + n。对于这类问题，一个技巧是通过构造，将其转化为齐次递推或更高维的线性递推。例如，令b_n = a_n + n + 1，可能可以消去常数项。更系统的方法是使用生成函数或特征方程，但这通常超出了普通算法竞赛的范围，更偏向数学竞赛。

4.3 实战：解决一个变体问题

假设有这样一道题：“定义数列g：g(1)=1, g(2)=1, g(n)=3*g(n-1) - 2*g(n-2) + 1 (n>2)。求g(n)对10^9+7取模的值，n <= 10^18。”

分析：这是二阶非齐次递推（带常数项1）。我们可以通过升维将其转化为齐次递推。 令h(n) = g(n) + c，我们希望找到常数c，使得h(n)的递推式没有常数项。 代入：h(n)-c = 3*(h(n-1)-c) - 2*(h(n-2)-c) + 1整理：h(n) = 3*h(n-1) - 2*h(n-2) + (1 - 3c + 2c + c) = 3*h(n-1) - 2*h(n-2) + (1 - 2c)令1 - 2c = 0，得c = 0.5。但模运算下处理分数麻烦。更通用的方法是构造状态向量： 令F(n) = [g(n), g(n-1), 1]^T，则有：

[ g(n) ] = [ 3 -2 1 ] [ g(n-1) ] [ g(n-1) ] [ 1 0 0 ] * [ g(n-2) ] [ 1 ] [ 0 0 1 ] [ 1 ]

这样，我们用一个3x3的矩阵就将非齐次项“吸收”了。接下来就可以用矩阵快速幂在O(log n)时间内求解。这个构造过程，是处理非齐次递推的关键技巧。

从斐波那契到Pell，看似在解两道不同的题，实则是在修炼同一种内功——对问题建模、分析复杂度、选择并优化算法的能力。下次当你遇到任何一个递推问题时，不妨按这个流程思考：它的递推式是什么阶数、什么形式？数据范围有多大？是单次查询还是多次查询？内存限制如何？回答完这些问题，最优解法往往就浮出水面了。在信息学奥赛的路上，这种系统性的思维训练，远比记住十道题的答案更有价值。