解题思路

Pell 数列：1, 2, 5, 12, 29, 70, …… 求第 n 项。

递推规律：

P(1) = 1 P(2) = 2 P(n) = 2 × P(n-1) + P(n-2)

验证：P(3) = 2×2+1 = 5，P(4) = 2×5+2 = 12 ✓

为什么要高精度？ n 最大 1000，Pell 数列第 1000 项有几百位数字，int 和 long long 都装不下，要用数组一位一位存。

怎么高精度算？

1. 用二维数组 f[i] 存第 i 项，每位数字一格
2. 逐位计算：f[i][j] = 2×f[i-1][j] + f[i-2][j]
3. 处理进位：某一位超过 10 就向高位进
4. 从高位到低位输出第 n 项

参考代码

#include <iostream>
using namespace std;

int f[1005][800];

int main() {
    int n;
    cin >> n;

    f[1][0] = 1;
    f[2][0] = 2;

    for (int i = 3; i <= n; i++) {
        for (int j = 0; j < 799; j++) {
            f[i][j] += 2 * f[i - 1][j] + f[i - 2][j];  // 递推
        }
        for (int j = 0; j < 799; j++) {  // 进位
            if (f[i][j] >= 10) {
                f[i][j + 1] += f[i][j] / 10;
                f[i][j] %= 10;
            }
        }
    }

    int p = 799;
    while (p > 0 && f[n][p] == 0) p--;
    for (int i = p; i >= 0; i--) cout << f[n][i];
    return 0;
}

复杂度分析

• 时间复杂度：O(N²)，n 项每项处理若干位
• 空间复杂度：O(N²)，存所有项的高精度数组