A3405. 小坤的数列【递归】
编程题
入门
知识点
题目描述
给定一个数列 $F$ 定义如下：
- 递推关系：
$F(x) =
\begin{cases}
F(x-1) + 2 \times F(x-3), & x > 3 \\
1, & x \leq 3
\end{cases}
$
- **任务**：编写一个程序，在**合理的时间复杂度**内计算并输出 $F(n)$ 的值。
- 递推关系：
$F(x) =
\begin{cases}
F(x-1) + 2 \times F(x-3), & x > 3 \\
1, & x \leq 3
\end{cases}
$
- **任务**：编写一个程序，在**合理的时间复杂度**内计算并输出 $F(n)$ 的值。
输入格式
输入仅一行，一个正整数 $n$
输出格式
输出仅一行，一个正整数，$F(n)$。
答案可能会超过 $2^{31}−1$，请使用 64 位整型存储。
答案可能会超过 $2^{31}−1$，请使用 64 位整型存储。
输入输出样例
输入 #1
5
输出 #1
5
说明/提示
数据范围
- $1≤n≤40$
- $1≤n≤40$