#9736. 【提高】Pell数列

【提高】Pell数列


Problem: Pell 数列

版权信息​:CCF-提高

任务总览

任务名称 时间限制 内存限制 分数
Pell 数列 1 sec 256 MB 100 points

题目描述

image


输入格式

一个整数 n。


输出格式

一个整数,表示 Pell 数列的第 n 项的值。


输入输出示例

输入示例 1

10

输出示例 1

2378

提示

  • 由于 n≤1000,可以使用 递推矩阵快速幂 方法高效计算 Pell 数列的第 n 项。

时间复杂度分析

方法 复杂度
递推计算 O(n)O(n)
矩阵快速幂 O(log⁡n)

对于 n≤1000,递推法即可高效计算答案。如果 n 较大(如 10910^9 级别),建议使用 矩阵快速幂 方法。