🐰😺🔢 兔猫信奥学院·加菲老师的泰波那契之谜 🔢😺🐰

在信奥学院的秘密花园里，三块古老的石碑依次排列，上面刻着神秘的数字法则。加菲老师对小兔和小猫说：“这是‘泰波那契’的魔法：

且对于所有 $n\ge0$，都有

现在，请你帮我计算第 $n$ 个泰波那契数 $T_n$！”

输入格式 📥

输入一行，包含一个整数 n，表示要求的泰波那契数的下标。

• $0 \le n \le 37$

输出格式 📤

输出一个整数，表示第 n 个泰波那契数 T_n 的值。

样例 1

4

4

• 解释：
  • $T_3 = T_0+T_1+T_2 = 0+1+1 = 2$
  • $T_4 = T_1+T_2+T_3 = 1+1+2 = 4$

样例 2

25

1389537

• 解释：
  通过递推可得 $T_{25}=1{,}389{,}537$。

🎓 加菲老师寄语：
泰波那契数列是经典的三项递推示例，通过本题，同学们可以体会如何用常量空间迭代维护多个状态。后续我们还会探索矩阵快速幂等高级技巧，用以高效计算更大范围的递推序列。

愿你们在信奥的旅程中，步步登高！