题解

按最后一步分类可得 $f_i=f_{i-1}+f_{i-2}+f_{i-3}$，初值为 $f_0=1,f_1=1,f_2=2$。只保留最近三项并在每次相加后取模。时间复杂度 $O(n)$，空间复杂度 $O(1)$。易错点：$n=0,1,2$ 必须单独处理。