🔍 第一步：精准理解题意（常被忽视却至关重要！）
题目中特别强调了：
“第1个数”和“第2个数”都为1 → 这意味着数列是：
F(1) = 1, F(2) = 1, F(3) = 2, F(4) = 3, F(5) = 5, …
✅ 不是从 F(0)=0 开始的版本！（信奥中务必紧盯下标定义！）
k 的范围是 1 ≤ k ≤ 46 → 这个约束非常关键，它暗示了什么？（先不揭晓，留给你思考：如果 k 是 10000 呢？现在为什么可以“放心”？）
📌 小挑战：请你在草稿纸上手动写出 项（标清序号），验证 F(19) 是否真的等于 4181？这个过程能帮你建立对递推关系的直觉。
🧠 第二步：思考“如何算出第 k 个数”？—— 探索不同策略
我们可以尝试几种思路，每种都值得深入追问：
递归写法（直觉最自然）
int fib(int k) {
if (k == 1 || k == 2) return 1;
return fib(k-1) + fib(k-2);
}
✅ 正确性？看起来完美匹配定义。
❓但试想：当 k = 40 时，fib(40) 会被调用多少次？fib(39) 和 fib(38) 又会各自重复计算大量子问题……
→ 这是典型的“重叠子问题”。你能估算一下 fib(46) 的递归调用次数数量级吗？（提示：它远超宇宙原子数 😅）
→ 信奥铁律：指数级算法在 k=46 时大概率超时！
递推（动态规划思想的雏形）
既然递归重复计算，能否“从小到大”依次算出 F(1), F(2), ..., F(k)？
需要存储哪些值？是否需要存全部？
空间上，我们真的需要一个长度为 46 的数组吗？还是只需记住最近两个数就够了？
→ 这引出了一个核心技巧：滚动数组 / 空间优化（DP 中极其高频！）
数学公式（Binet 公式）？
虽然存在闭式解，但在整数运算、精度、取整误差等方面对信奥选手并不友好，且不符合训练目标。
→ 信奥更看重你对“计算过程”的掌控力，而非套公式。
🛠️ 第三步：动手设计你的算法（系统化步骤）
试着按这个流程梳理你的代码逻辑：
步骤 你要回答的问题 信奥考点提示
① 输入处理 如何读入 k？是否需校验范围？（本题保证合法，但竞赛中边界检查是好习惯） cin >> k; 基础IO
② 特殊情况处理 k == 1 或 k == 2 时，能否直接返回？避免后续循环开销 边界特判（提升鲁棒性）
③ 主体递推 用几个变量？循环从几开始？到几结束？每次更新如何保证“前两项”始终可用？ 状态转移方程：f_curr = f_prev1 + f_prev2；变量轮换技巧
④ 输出 直接输出结果即可，注意无多余空格/换行 格式即得分点！
💡 关键启发：
把“计算第 k 项”想象成接力赛：
第1棒：a = 1（F₁）
第2棒：b = 1（F₂）
第3棒：c = a + b → 此时 a, b 要更新为 b, c，才能跑第4棒……
你只需要3个变量，就能跑完所有46棒！
✅ 最后，请你尝试完成以下任务（这是你真正的练习）：
在纸上画出 k=5 时，三个变量（比如 f1, f2, f3）在每次循环中的值变化表；
写出 C++ 代码框架（不必运行，但要确保逻辑自洽）；
思考：若题目改为 k ≤ 10^6，且要求模 10^9+7，你的解法需要做哪些调整？
