题解

思路

令 $f_n$ 表示长度恰好为 $n$ 的合法序列数。观察最后一个块：它要么是一朵红花，要么是一组 $k$ 朵白花。因此

空序列是拼接的起点，所以 $f_0=1$。所有运算均对 $10^9+7$ 取模。

做法

先读入所有询问并记最大右端点 $B$，按照递推式计算 $f_1,\ldots,f_B$。再建立前缀和

询问 $[a,b]$ 的答案为 $(s_b-s_{a-1})\bmod(10^9+7)$。

正确性证明

对于任意长度为 $n$ 的合法序列，最后一个块只有两种互斥情况：

• 最后是单朵红花。删去它后，得到任意一个长度为 $n-1$ 的合法序列，共 $f_{n-1}$ 种；
• 最后是连续 $k$ 朵白花。仅当 $n\ge k$ 时可行，删去该块后得到任意一个长度为 $n-k$ 的合法序列，共 $f_{n-k}$ 种。

两类覆盖全部合法序列，因此递推式正确。前缀和 $s_b-s_{a-1}$ 恰好累加所有长度 $a$ 到 $b$ 的方案数，所以每个询问的输出正确。

复杂度分析

设所有询问的最大右端点为 $B$。预处理时间复杂度 $O(B)$，回答询问共需 $O(t)$，空间复杂度 $O(B)$。