BISHI62　斐波那契数列¶

简单通过率 41.22%python3样例通过牛客 AC基础数学递归

一句话

求 F_k mod (1e9+7)，F_1 = F_2 = 1，k <= 1e6。

解题思路¶

这题考什么¶

最基础的线性递推，重点在于怎么把递推写成迭代，以及什么时候取模。

递推式 F_i = F_{i-1} + F_{i-2} 每一步只依赖前两项，所以不必开长度为 k 的数组，用两个变量滚动即可：循环不变量是「进入第 j 轮之前，a = F_{j-1}、b = F_j」，每轮把这对值往后推一格。初值取 a, b = 0, 1，正是 (F_0, F_1) （补一个 F_0 = 0 能让递推从头就成立，省掉对 k = 1、2 的特判）。要拿到 F_k，从 (F_0, F_1) 出发推 k-1 步即可。

照定义写成递归 fib(k) = fib(k-1) + fib(k-2) 是两条歧路：不加记忆化时调用次数与 F_k 同阶，指数爆炸；加了记忆化虽然是 O(k)，但 k = 1e6 的递归深度远超 Python 默认的 1000 层递归上限，会直接崩栈。迭代版没有这两个问题。

k <= 1e6，O(k) 递推就够，不需要矩阵快速幂 / 快速倍增（那是 k 到 1e18 时才必要的，见 81-快速幂与逆元）。

数据规模与复杂度¶

k <= 1e6，单组数据。O(k) 循环 ≈ 1e6 次「加法 + 取模」，Python 约 0.2s，时限 2 秒（其他语言）绰绰有余；空间 O(1)，只有两个变量。注意不要算精确大整数 F_k 再取模：F_1e6 有 20 多万位，大整数加法本身是 O(位数)，总复杂度会退化成 O(k^2 / 64)，直接 TLE。每一步都取模，把数值钉死在 30 位以内，加法才是真正的 O(1)。

坑在哪¶

下标从 1 开始，F_1 = F_2 = 1；k = 1 或 2 都输出 1。 k = 1 时 range(k-1) 是空循环，b 保持初值 1，答案正确 —— 初值选 (0, 1) 就是为了让这个边界自动成立；
循环里用元组交换 a, b = b, (a+b) % MOD，右侧先整体求值再赋值，不需要临时变量，也不会出现「先改了 a 导致 b 用到新值」的顺序错误；
取模不能省，理由见上；而且只取一次模就够 —— 两个小于 MOD 的数相加不会超过 2*MOD，一次 % 必定落回区间；
模数是 1e9+7 = 1000000007，写成 1e9+7 会得到浮点数，必须写整数字面量。

样例复核¶

k = 19。从 (0,1) 推 18 步，b 依次是 1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181，最后一项 4181 就是 F_19，与样例一致 ✓。

递推与递归的取舍见 85-基础数学与递推。

参考实现¶

solutions/BISHI62.py
import sys

MOD = 1000000007                 # 必须是整数字面量，1e9+7 会变成浮点
k = int(sys.stdin.buffer.read().split()[0])
a, b = 0, 1                      # a = F_0, b = F_1
# 不变量：每轮结束后 a = F_j、b = F_{j+1}；推 k-1 步后 b 即为 F_k
for _ in range(k - 1):           # k = 1 时空循环，b 保持 F_1 = 1
    a, b = b, (a + b) % MOD      # 每步取模，避免大整数退化
sys.stdout.write(str(b % MOD) + "\n")   # b 已在模内，这次取模只是兜底

BISHI62 斐波那契数列¶