题解

$f_i$ 等于前面至多 $k$ 项之和：$f_i=\sum_{j=1}^{k}f_{i-j}$，越界项忽略，且 $f_0=1$。若每次重新求和会达到 $O(nk)$。维护变量 window 表示当前所需区间和：加入新算出的 $f_i$，并在窗口超过 $k$ 项时减去 $f_{i-k}$。时间复杂度 $O(n)$，空间复杂度 $O(n)$。减法后要加模数防止负数。