Pell数列递推求解与取模优化C++实现

## 📝 问题分析 这道题要求计算 **Pell 数列** 的第 `k` 项，并对 **32767** 取模。 递推公式为： \[ a_1 = 1, \quad a_2 = 2, \quad a_n = 2 \cdot a_{n-2} + a_{n-1} \quad (n > 2) \] 由于输入有多个 `n`（最多可能很大），直接递推到最大值即可，**避免重复计算**。 --- ## 🧠 解题思路 1. **递推预处理**：因为每个查询的 `x` 可能不同，我们可以先将 `a[1]` 到 `a[max_x]` 全部计算出来并存储，时间复杂度 \(O(\text{max\_x})\)。 2. **取模运算**：每一步计算时都进行 `% 32767`，防止溢出（虽然 `long long` 也安全，但取模是必须的）。 3. **查询输出**：预处理完后，对每个询问直接输出 `a[x]`。 --- ## 💻 C++ 代码实现 ```cpp #include <iostream> #include <vector> using namespace std; const int MOD = 32767; int main() { int n; cin >> n; // 读入所有询问，并找出最大值 vector<int> queries(n); int max_x = 0; for (int i = 0; i < n; i++) { cin >> queries[i]; max_x = max(max_x, queries[i]); } // 预处理 Pell 数列 vector<int> a(max_x + 1); if (max_x >= 1) a[1] = 1 % MOD; if (max_x >= 2) a[2] = 2 % MOD; for (int i = 3; i <= max_x; i++) { a[i] = (2 * a[i - 2] + a[i - 1]) % MOD; } // 输出结果 for (int i = 0; i < n; i++) { cout << a[queries[i]] << endl; } return 0; } ``` --- ## 📊 代码说明 | 部分 | 说明 | |------|------| | `vector<int> queries(n)` | 存储所有询问值 | | `max_x` | 找出最大需要计算的项数，避免浪费计算 | | `a[1]`、`a[2]` | 初始条件，记得取模 | | `a[i] = (2*a[i-2] + a[i-1]) % MOD` | 核心递推公式，防止溢出 | | 输出结果 | 根据原输入顺序输出 | --- ## ⚠️ 注意事项 - **数组大小**：`max_x` 可以到多大？题目没有明确限制，但用 `vector` 动态分配，安全且高效。 - **取模**：必须每一步都取模，因为递推后期数值会非常大（增长速度类似斐波那契，但系数为 2）。 - **边界情况**：若 `max_x` 为 0 或 1，需特殊处理数组大小（代码已考虑）。 - **性能**：时间复杂度 \(O(\max\_x)\)，空间复杂度 \(O(\max\_x)\)，完全满足常见竞赛要求。 --- ## 🚀 扩展建议 - 若 `n` 很大且查询数较少，可考虑 **矩阵快速幂** 单次求解，时间复杂度 \(O(\log k)\)，避免预处理所有项。 - 本题模数为 32767，若需要大批量查询，也可以考虑 **循环节**（因为模数较小，数列会有周期性），但这里预处理已足够。 --- ######[AI写代码神器 | 857点数解答 | 2026-07-31 19:50:46]