P4721 Pell数列（基础）

解题思路

第一步：看懂题目和规律。 Pell 数列的规律是：第一项 a1=1，第二项 a2=2，从第三项开始，每一项都等于前一项的 2 倍再加上前前一项，公式就是 an = 2×a(n-1) + a(n-2)。题目要求第 k 项除以 32767 的余数，其中 k 最大可以到 999999（注意是小于 1000000）。

第二步：想到“预处理”的思想。 把 Pell 数列想成一条长长的路，每一项都要靠前面的项推出来。如果每组数据都从头开始重新推一遍，当数据组数很多、k 又很大的时候就会重复计算很多次，非常浪费。聪明的做法是：先把从第 1 项到第 999999 项全部算好，存进一个数组里，就像提前编好一本“数列字典”。之后每次查询第 k 项，直接翻字典读出 pell[k] 就可以了。

第三步：处理好取模。 题目只要求输出模 32767 的余数，而余数运算是可以“边走边取模”的：因为 (2×a+b) mod 32767 = (2×(a mod 32767) + (b mod 32767)) mod 32767。所以在递推的每一步都先取一次模，中间的数就不会变得很大，永远不会超出 int 的范围，结果也不会错。这就像做大数除以 32767 时每次只保留余数继续算，道理是一样的。

第四步：注意边界情况。 k=1 时直接输出 1，k=2 时直接输出 2，这两个是数列的初值，循环从第 3 项开始即可。

第五步：加速读入输出。 输入输出数据量可能比较大，所以代码里用 scanf 和 printf 快速读入输出，会比 cin、cout 快不少。

参考代码

// Pell数列：a[i]=2*a[i-1]+a[i-2]，预处理前1000000项模32767
#include <cstdio>
int pell[1000005];  // 全局数组存 Pell 数列每一项的余数，避免栈溢出
int main() {
    pell[1] = 1; pell[2] = 2;
    for (int i = 3; i < 1000000; i++)
        pell[i] = (2 * pell[i-1] + pell[i-2]) % 32767;  // 递推并取模
    int cnt, k;
    scanf("%d", &cnt);
    while (cnt--) {
        scanf("%d", &k);
        printf("%d\n", pell[k]);
    }
    return 0;
}

复杂度分析

程序先把第 1 到第 999999 项全部递推一遍，这个过程只需要一层循环，时间复杂度是 O(1000000)，也就是 O(1e6)。预处理完成之后，每一组查询只需要直接输出数组中的一项，是 O(1) 的。总的时间复杂度为 O(1000000 + cnt)，完全能够承受。空间上用一个长度约 100 万的 int 数组存储所有答案，内存大约 4MB，在题目限制之内。之所以选择预处理而不是每组查询都从头递推，是因为 k 的最大值接近 100 万，如果测试数据有上万组，每组都重算一遍就要重复计算上亿次，白白浪费大量时间；而预处理只计算一次，之后每次查询都是一步直达，速度优势非常明显。这正是“以空间换时间”的常用技巧：多花一点内存把答案提前存好，换来的是查询时的极快响应。