考虑只能放 11 个或者 kk 个，那么设 fif_i 表示长度为 ii 的字符串的方案，那么显然有：

fi=fi−1+fi−kf_{i}=f_{i-1}+f_{i-k}

询问区间，那么做前缀和，时间复杂度为 O(n+T)O(n+T)。