1. 项目概述从一道经典信息学奥赛题说起最近在整理一些信息学奥赛OI的经典题目时又翻到了Pell数列这道题。它经常出现在NOIP全国青少年信息学奥林匹克联赛和各省市选拔赛的初、中级组别中考察点非常明确递推、大数处理和基本的编程思维。很多刚接触算法竞赛的同学第一次遇到它时可能会被其看似简单的递推公式所迷惑结果一提交就发现要么超时要么答案错误。这道题就像一块“试金石”能很好地检验你是否真正理解了递推与取模运算的精髓而不仅仅是背下了公式。简单来说题目会给你一个递推公式a1 1, a2 2, an 2 * a(n-1) a(n-2) (n2)。然后询问你第k项的值。难点在于k的值可能非常大比如几十万甚至上百万直接递归计算铁定超时同时数列增长非常快第几万项的值就可能远超任何基本数据类型的范围所以必须对结果取模通常是取模32767。这要求我们必须在迭代计算的过程中每一步都及时取模才能保证在时间和空间上都可行。接下来我就结合自己带学生刷题的经验把这道题的解题思路、代码实现细节以及那些容易踩的“坑”掰开揉碎了讲清楚。2. 核心思路拆解为什么不能直接递归2.1 理解Pell数列的增长特性首先我们得正视Pell数列的增长速度。根据公式an 2*a(n-1) a(n-2)这是一个线性齐次递推关系。我们可以通过其特征方程x^2 2x 1来近似了解其通项解得特征根为1±√2。由于1√2 ≈ 2.414这意味着数列的通项近似于C * (2.414)^n。这是一个指数级别的增长。让我们做个简单的估算a11, a22, a35, a412, a529, a670, a7169...。可以看到仅仅到第7项数值已经达到169。如果计算到第30项数值将是一个巨大的天文数字远超long long64位整数最大值约9e18的表示范围。题目要求对32767取模正是为了将结果控制在一个小范围内但计算过程本身必须能处理这种大数增长带来的溢出问题。注意这里说的“溢出”不是指最终答案溢出而是计算中间过程。即使最终答案要对32767取模但如果你在计算2*a(n-1) a(n-2)时a(n-1)本身已经是一个巨大的数尽管它可能已经取过模乘以2后可能超出你所用数据类型的临时存储范围导致中间结果溢出从而得到错误的取模前数值最终导致答案错误。这是第一个关键点。2.2 递归 vs. 迭代的抉择面对递推公式新手的直觉往往是写一个递归函数int Pell(int n) { if (n 1) return 1; if (n 2) return 2; return (2 * Pell(n-1) Pell(n-2)) % 32767; }这段代码简洁明了但存在致命问题时间复杂度过高。对于每个Pell(n)它需要调用两次自身这形成了一个指数爆炸的递归树。计算Pell(30)所需的递归调用次数已经非常庞大更不用说题目中常见的n上限可能达到1000000。这必然导致超时TLE。因此我们必须采用迭代法动态规划。既然每一项只依赖于前两项我们完全可以用循环从第3项开始一步步计算到第n项同时在这个过程中及时取模。这样时间复杂度是O(n)对于百万级别的n也是可以接受的在1秒时限内。空间上我们甚至不需要保存整个数列只需要两个变量滚动记录前两项即可空间复杂度O(1)。2.3 取模运算的时机与原理这是本题最核心的考点之一。为什么可以在计算过程中取模而不影响最终结果的正确性这基于模运算的一个基本性质(a b) % m ((a % m) (b % m)) % m(a * b) % m ((a % m) * (b % m)) % m对于我们的递推式an 2*a(n-1) a(n-2)假设我们要计算an % MODMOD32767。根据上述性质an % MOD (2*a(n-1) a(n-2)) % MOD ((2*a(n-1)) % MOD a(n-2) % MOD) % MOD ( (2 * (a(n-1) % MOD)) % MOD (a(n-2) % MOD) ) % MOD这意味着我们只需要始终保存a(n-1)和a(n-2)对 MOD 取模后的结果就能正确计算出an对 MOD 取模后的结果。我们完全不需要知道a(n-1)和a(n-2)的真实巨大值是多少。这完美解决了大数溢出的问题。3. 代码实现与逐行解析理解了原理我们来看C代码实现。我会提供两个版本一个是基础易懂的数组版本另一个是更优的空间滚动版本并解释每一行代码的意图和注意事项。3.1 版本一使用数组存储直观版这个版本适合初学者理解它显式地用一个数组a[]来存储每一项取模后的结果。#include iostream using namespace std; const int MOD 32767; // 定义模数常量便于修改和维护 int main() { int n, k; cin n; // 读取询问的个数 // 预处理计算可能需要的最大项。通常题目会给出最大的k值这里假设我们已知或动态处理。 // 更常见的做法是对于每个k单独计算。但我们可以先询问所有k找到最大值然后一次性预处理。 // 这里为了讲解我们先采用对每个k单独计算的逻辑在3.2版本展示预处理。 for (int i 0; i n; i) { cin k; // 读取第i次询问的项数 if (k 1) { cout 1 endl; continue; } if (k 2) { cout 2 endl; continue; } // 动态申请数组大小为 k1为了下标从1开始更直观 // 注意如果k很大例如10^6在递归函数中开这么大数组会导致栈溢出。 // 但这里在main函数中数组开在堆栈上对于极大的k如10^7可能仍会导致栈溢出。 // 更安全的方法是使用vectorint a(k1)或者直接用滚动变量。 int* a new int[k1]; // 使用动态内存分配避免栈溢出风险 a[1] 1; a[2] 2; for (int j 3; j k; j) { // 核心计算与取模 // 先计算 2*a[j-1]结果可能超过int范围吗考虑MOD32767a[j-1] MOD。 // 2 * 32766 65532仍在int范围内。但为了通用性先取模更安全。 a[j] (2 * a[j-1] a[j-2]) % MOD; } cout a[k] endl; delete[] a; // 释放动态数组防止内存泄漏 } return 0; }代码要点解析常量定义将模数32767定义为MOD是良好的编程习惯。一来提高代码可读性二来如果模数改变只需修改一处。输入格式处理题目通常是先输入询问次数n然后跟着n个k。代码通过一个循环处理多次询问。边界条件处理对于k1和k2的情况直接输出避免进入循环。这是必要的因为我们的循环从j3开始。数组大小与内存声明int a[k1]在栈上时如果k很大比如100万栈空间通常几MB可能不足导致运行时错误栈溢出。因此这里使用了new进行动态内存分配从堆heap中申请空间堆空间通常远大于栈。务必记得用delete[]释放。取模运算的位置在for循环内部计算完2*a[j-1] a[j-2]后立即对MOD取模并将结果赋给a[j]。这保证了数组中存储的每一个值都是已经取过模的不会超过MOD从而使得后续计算中的乘法2*a[j-1]不会溢出。3.2 版本二滚动变量优化推荐版数组版本虽然直观但当k很大时每次询问都申请和释放一个大小为k1的数组会有一定的内存和时间开销。更重要的是我们观察到计算a[j]时只依赖于a[j-1]和a[j-2]。我们完全不需要保存整个数列只需要两个变量像“滚动”一样不断更新前两项的值即可。这被称为滚动数组思想能将空间复杂度从O(n)降到O(1)。#include iostream using namespace std; const int MOD 32767; int main() { int n, k; cin n; for (int i 0; i n; i) { cin k; if (k 1) { cout 1 endl; continue; } if (k 2) { cout 2 endl; continue; } // 使用三个变量进行滚动计算 int prev2 1; // 代表 a[j-2]初始为 a1 int prev1 2; // 代表 a[j-1]初始为 a2 int current; // 代表 a[j] for (int j 3; j k; j) { // 计算当前项 current (2 * prev1 prev2) % MOD; // 滚动更新变量为下一次迭代做准备 prev2 prev1; prev1 current; } // 循环结束时prev1 就是 a[k] 的值 cout prev1 endl; } return 0; }代码要点解析变量命名prev2,prev1,current清晰地表明了它们代表的是数列中的哪一项比简单的a, b, c更易读。滚动更新逻辑这是核心。计算完current即新的a[j]后为了计算下一项a[j1]我们需要a[j-1]和a[j]。所以让prev2变成原来的prev1即a[j-1]让prev1变成current即a[j]。这个过程就像把窗口向后滑动了一格。最终结果当循环结束时j的值为k1prev1恰好是第k项的值因为最后一次迭代计算的是a[k]并赋给了current然后prev1被更新为current。所以直接输出prev1即可。优势这个版本完全避免了数组的使用无论k多大都只使用固定的几个整型变量。内存效率极高且减少了内存分配释放的开销速度也更快。3.3 版本三预处理与查询分离高效版在实际竞赛中如果询问次数n非常多比如10万次而k的范围是有限的比如不超过10万那么对每次询问都从头计算Pell(k)会导致大量的重复计算总时间复杂度为O(n * max(k))可能会超时。更高效的做法是预处理先读取所有询问找到其中最大的k_max然后一次性计算出从第1项到第k_max项的所有结果存储在一个数组里。之后对于每个询问都可以通过O(1)的时间直接输出结果。这样总时间复杂度是O(k_max n)。#include iostream #include vector #include algorithm // 用于max函数 using namespace std; const int MOD 32767; const int MAX_K 1000000; // 根据题目可能的最大值设定或者动态确定 int main() { int n; cin n; vectorint queries(n); // 存储所有询问的k值 int max_k 0; // 第一遍读入收集所有询问并找到最大值 for (int i 0; i n; i) { cin queries[i]; if (queries[i] max_k) { max_k queries[i]; } } // 预处理计算从1到max_k的所有Pell数取模后 vectorint pell(max_k 1); // 下标从1开始 if (max_k 1) pell[1] 1; if (max_k 2) pell[2] 2; for (int j 3; j max_k; j) { // 注意这里pell[j-1]和pell[j-2]已经是取模后的值 pell[j] (2 * pell[j-1] pell[j-2]) % MOD; } // 第二遍输出直接查表回答每个询问 for (int k : queries) { cout pell[k] endl; } return 0; }代码要点解析两遍处理第一遍循环只读入和记录所有k值并找出最大值max_k。第二遍循环才进行输出。这要求我们能够存储所有询问通常使用vector。预处理数组我们声明一个vectorint pell(max_k 1)。这里使用vector比动态数组new更安全方便因为它自动管理内存。预处理循环从3计算到max_k填充这个数组。边界检查在给pell[1]和pell[2]赋值前需要判断max_k是否大于等于1或2防止下标越界。查询效率预处理完成后回答每个询问只是简单的数组查找pell[k]时间复杂度O(1)非常适合询问量大的场景。空间权衡这个方法需要O(max_k)的空间来存储整个数列。如果max_k非常大比如1亿可能会超出内存限制256MB内存大约能存下6千万个int。这时就需要权衡或者回到滚动计算的方法。但针对本题常见的范围k ≤ 10^6使用vector预处理是完全可行的。4. 关键细节与常见“坑点”在实际编写和调试代码时以下几个细节至关重要一不留神就会丢分。4.1 整数溢出与中间过程取模这是最隐蔽的错误。请看下面这段有问题的代码// 错误示例 int current (2 * prev1 % MOD prev2) % MOD; // 看似正确实则危险问题出在哪里假设prev1 20000,MOD 32767。2 * prev1 40000这个值本身没有超过int范围约21亿。但如果我们先计算2 * prev1 % MOD即40000 % 32767 7233然后再加prev2。这似乎没问题。但考虑通用性如果递推式是an 100000 * a(n-1) a(n-2)模数还是32767。100000 * prev1就极有可能在取模前就溢出。安全的做法是在每一次乘法和加法之后都立即考虑取模或者使用更大范围的数据类型来承载中间结果。对于本题2 * prev1因为prev1 MOD32767所以2*prev1 65534在int范围内是安全的。但养成“先乘后立即取模”或“使用long long暂存”的习惯更好// 更安全的写法之一使用long long暂存中间结果 long long temp 2LL * prev1 prev2; // 使用LL确保是long long乘法 int current temp % MOD; // 更安全的写法之二分步取模适用于模运算性质 int current ( (2 * (prev1 % MOD)) % MOD (prev2 % MOD) ) % MOD; // 由于prev1和prev2本来就小于MOD所以简化为 int current (2 * prev1 prev2) % MOD; // 对于本题这样写是安全的结论在算法竞赛中只要涉及到可能的大数乘法和取模无脑使用long long来存储中间计算结果是一个省心且安全的策略。4.2 边界条件n1 和 n2 的处理在滚动变量版本的循环中我们是从j3开始的。如果用户输入的k是1或2这个循环就不会执行。此时变量prev1和prev2还保持着初始值2和1。如果我们错误地输出prev1对于k1的情况就会得到错误答案2。因此必须在循环开始前对k1和k2的情况进行特判这是编写递推/动态规划代码时必须养成的习惯。数组版本同样需要特判否则访问a[1]和a[2]可能是未初始化的值。4.3 输入输出效率与同步在信息学奥赛中当输入输出数据量很大时例如n和k都是十万、百万级别C默认的cin/cout可能会因为与C标准输入输出的同步而变得很慢导致超时。有两种常见的优化方法在main函数开头添加同步关闭语句ios::sync_with_stdio(false); cin.tie(nullptr);ios::sync_with_stdio(false)用于关闭C标准流与C标准流的同步可以大幅提升cin/cout的速度。关闭后不要混用printf/scanf和cin/cout。cin.tie(nullptr)用于解除cin和cout的绑定默认情况下每次cin操作前都会刷新cout缓冲区这会影响效率。解除后可以进一步提升速度但需确保在需要时手动刷新例如在交互题中输出提示后需要立即刷新才能看到。使用scanf和printf C语言的scanf和printf在输入输出大量数据时通常比未优化的cin/cout快。对于本题这种只读入数字的场景使用scanf更简单直接。#include cstdio // 包含scanf/printf int main() { int n, k; scanf(%d, n); for (int i 0; i n; i) { scanf(%d, k); // ... 计算过程 ... printf(%d\n, result); } return 0; }建议在竞赛编程中如果不涉及字符串混合输入输出直接使用scanf/printf是简单高效的选择。如果习惯使用cin/cout务必记得加上那两行加速语句。4.4 内存管理数组大小与栈溢出正如在3.1版本中提到的在函数内部包括main函数声明大数组如int a[1000000]可能会占用大量栈空间导致栈溢出Stack Overflow。在在线评测系统OJ中栈空间通常是有限的比如8MB。安全做法对于需要大型数组的情况使用vector其数据存储在堆上。或者使用动态分配new/delete如3.1版本所示但要注意配对释放。最好的方法是如果可能采用滚动变量法避免使用大数组。5. 性能分析与优化探讨对于Pell数列这个问题O(n)的迭代解法已经是最优的时间复杂度了因为我们必须至少计算前n项才能知道第n项的值。但在一些变体问题或者极端约束下我们还可以探讨一些更深入的话题。5.1 矩阵快速幂应对超大n的挑战如果题目中的n大到离谱比如10^18O(n)的算法也无法胜任。这时就需要用到矩阵快速幂来求解线性递推数列的第n项时间复杂度可以降到O(log n)。Pell数列的递推式an 2*a(n-1) a(n-2)可以写成矩阵形式[ a_n ] [ 2 1 ] * [ a_(n-1) ] [ a_(n-1) ] [ 1 0 ] [ a_(n-2) ]进而推导出[ a_n ] [ 2 1 ]^(n-2) * [ a_2 ] [ a_(n-1) ] [ 1 0 ] [ a_1 ]这样问题转化为计算矩阵[2, 1; 1, 0]的(n-2)次幂。利用快速幂算法可以在O(log n)的时间内完成矩阵的幂运算从而得到a_n。虽然本题通常不需要但掌握矩阵快速幂是解决线性递推问题的终极武器对于斐波那契数列等问题的超大项计算是必备技能。5.2 取模运算的常数优化取模运算%在CPU中是比较耗时的操作。在本题的循环中我们每次迭代都要做一次取模。当n极大时这个开销累积起来也不小。有没有优化空间观察模数MOD 32767这是一个比较小的数。我们可以利用一个技巧因为我们在计算current 2*prev1 prev2时prev1和prev2都小于MOD所以2*prev1 prev2 2*MOD MOD 3*MOD 98301。这个值仍然在int范围内。我们可以延迟取模累积几次加法后再取模以减少取模运算的次数。但我不建议在竞赛中做这种微优化除非性能分析明确表明这里是瓶颈。理由如下代码可读性降低。容易出错需要仔细计算上界。现代编译器的优化已经非常智能简单的%操作可能被优化得很好。对于本题的规模n在百万级O(n)次取模运算完全在1秒时限内。保持代码的清晰和正确性远比一点常数优化重要。6. 测试用例与调试技巧写完代码后必须用多种测试用例进行验证。6.1 标准测试用例基础验证输入n5,k分别为1, 2, 3, 4, 5预期输出1, 2, 5, 12, 29目的验证递推公式和边界条件是否正确。取模验证计算一些项数较大的值手动验证或写一个暴力程序用Python的大整数计算真实值后取模与你的程序结果对比。例如可以计算第10项、第20项的值进行比对。大数输入输入n1,k100000目的测试程序在大输入下的运行时间和内存使用是否正常是否有溢出风险。多次询问输入n100000所有k随机在1到100000之间。目的测试预处理版本版本三的效率以及输入输出优化是否有效。6.2 调试技巧输出中间过程当你对结果有疑问时最有效的调试方法之一是输出中间计算过程。例如在滚动版本中可以在循环内打印每一步的prev2,prev1,current值。for (int j 3; j k; j) { current (2 * prev1 prev2) % MOD; // 调试输出 // cout j j : prev2 prev2 , prev1 prev1 , current current endl; prev2 prev1; prev1 current; }通过观察前几项的计算值可以快速定位是递推公式写错了还是取模逻辑有问题或者是变量滚动更新顺序错了。6.3 常见错误对照表错误现象可能原因解决方法输出结果错误对小k1. 边界条件k1,2未特判。2. 递推公式写错如符号错误。3. 变量初始值赋值错误。1. 添加if(k1)... if(k2)...。2. 仔细检查公式2*prev1 prev2。3. 检查prev21, prev12。输出结果错误对大k1. 整数溢出中间计算未取模或未用long long。2. 取模运算时机或方式错误。1. 使用long long存储中间结果或确保每次运算后立即取模。2. 确认取模公式(2*prev1 prev2) % MOD。程序运行超时TLE1. 使用了递归算法。2. 对多次询问未预处理每次都O(k)计算。3.cin/cout未关闭同步。1. 改用迭代循环。2. 采用预处理查表法版本三。3. 添加ios::sync_with_stdio(false); cin.tie(nullptr);或改用scanf/printf。程序运行时错误如段错误1. 数组开在栈上k太大导致栈溢出。2. 动态数组new后未delete某些OJ可能报错。3. 访问了数组越界如pell[k]但k可能为0。1. 使用vector或滚动变量法。2. 确保new和delete[]配对。3. 检查输入范围确保数组下标有效。7. 举一反三类似题型与思维扩展Pell数列是线性递推数列的一个典型代表。掌握它就掌握了一类问题的通用解法。斐波那契数列Fibonacci递推式F(n) F(n-1) F(n-2)。解法一模一样只是系数和初始值不同。同样需要注意大数取模和迭代计算。爬楼梯问题一次可以爬1级或2级台阶问爬到第n级有多少种方法。其递推式就是斐波那契数列。更复杂的线性递推例如a(n) p*a(n-1) q*a(n-2) r*a(n-3)。这时滚动变量就需要3个prev3, prev2, prev1但核心思想不变迭代计算及时取模。带常数项的递推例如a(n) 2*a(n-1) 3。这类问题可以通过构造等比数列或者矩阵快速幂来解决。核心思维对于任何递推问题先写出准确的递推公式和初始条件。然后分析数据范围决定是否需要取模。最后根据项数n的大小选择算法n小如30可以用递归n中等如10^7用迭代/动态规划n巨大如10^12则必须用矩阵快速幂。回过头看Pell数列这道题它简洁地融合了递推、取模、迭代优化这几个基础而重要的知识点。我带的很多学生都是通过这道题真正理解了“在循环中取模”的意义以及如何将数学公式转化为高效、健壮的代码。希望这篇详细的拆解能帮助你不仅AC这道题更能触类旁通解决一系列类似的竞赛题目。