CSP-J 2025 第一轮 第 8 题：f[0]=f[1]=1，f[n]=(f[n-1]+f[n-2])%7，求 f[2

题目

已知 $f[0] = 1$, $f[1] = 1$，并且对于所有 $n \geq 2$ 有 $f[n] = (f[n-1] + f[n-2]) \% 7$。那么 $f[2025]$ 的值是多少？

选项

• A. $2$
• B. $4$
• C. $5$
• D. $6$

答案

D

题解

这题可以通过寻找递推数列的周期来做，答案是 D，6。

% 7 表示除以 7 后的余数。按照递推式逐项计算：

例如，$f[5]=(5+3)\%7=1$，$f[6]=(1+5)\%7=6$。

注意到 $f[16]=1$、$f[17]=1$，与最开始的 $f[0]=1$、$f[1]=1$ 完全相同。由于每一项都只由前两项决定，从这里开始，后续数值会按照同样的顺序重复。因此，16 是这个数列的一个周期，即

$$ f[n+16]=f[n]. $$

这里必须找到连续两项同时重复；仅仅出现某一个相同的数，还不能保证后续序列也相同。

因为

$$ 2025=16\times126+9, $$

所以

$$ f[2025]=f[9]=6. $$

故选 D。