Problem: Pell 数列

​版权信息​：CCF-提高

任务总览

题目描述

输入格式

一个整数 n。

输出格式

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

输入输出示例

输入示例 1

10

输出示例 1

2378

提示

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

时间复杂度分析

对于 n≤1000，递推法即可高效计算答案。如果 n 较大（如 $10^9$ 级别），建议使用 矩阵快速幂 方法。