#9736. 【提高】Pell数列
【提高】Pell数列
Problem: Pell 数列
版权信息:CCF-提高
任务总览
任务名称 | 时间限制 | 内存限制 | 分数 |
---|---|---|---|
Pell 数列 | 1 sec | 256 MB | 100 points |
题目描述
输入格式
一个整数 n。
输出格式
一个整数,表示 Pell 数列的第 n 项的值。
输入输出示例
输入示例 1
10
输出示例 1
2378
提示
- 由于 n≤1000,可以使用 递推 或 矩阵快速幂 方法高效计算 Pell 数列的第 n 项。
时间复杂度分析
方法 | 复杂度 |
---|---|
递推计算 | O(n)O(n) |
矩阵快速幂 | O(logn) |
对于 n≤1000,递推法即可高效计算答案。如果 n 较大(如 级别),建议使用 矩阵快速幂 方法。