A93777 拼花带 解题报告

1. 题意分析

红色花带片长度为 $1$，白色花带片长度为 $k$。
$f(n)$ 表示恰好拼成长度 $n$ 的不同拼法数量。

现有 $t$ 次询问，每次给出区间 $[a,b]$，求：

$$\sum_{n=a}^{b} f(n) \pmod{10^9+7}$$

数据范围

• $1 \le t,k \le 10^5$
• $1 \le a_i \le b_i \le 10^5$

样例说明（$k=3$）：

• $f(0)=1$：空拼法，作为递推基准
• $f(1)=1,\ f(2)=1$
• $f(3)=f(2)+f(0)=2$
• $f(4)=f(3)+f(1)=3$
• $f(5)=f(4)+f(2)=4$
• $f(6)=f(5)+f(3)=6$

2. 递推公式推导

凑成长度 $n$ 有两种选择：

1. 最后放红色花带（长度1）：前面拼出 $n-1$，方案数 $f(n-1)$
2. 最后放白色花带（长度k）：仅当 $n \ge k$，前面拼出 $n-k$，方案数 $f(n-k)$

递推式：

$$\begin{cases} f(0)=1 \\ f(n)=f(n-1) & 1\le n < k \\ f(n)=f(n-1)+f(n-k) & n \ge k \end{cases}$$

定义前缀和数组 $S[n]=\sum_{i=0}^{n}f(i) \bmod (10^9+7)$。
对于查询区间 $[a,b]$：

$$ans = (S[b]-S[a-1] + \text{MOD}) \bmod \text{MOD}$$

加上 MOD 再取模，避免减法得到负数。

3. 算法复杂度

• DP预处理：$O(\text{MAX})$，$\text{MAX}=10^5$
• 前缀和预处理：$O(\text{MAX})$
• 每次查询 $O(1)$，全部查询 $O(t)$
• 总复杂度 $O(10^5 + t)$，可以通过全部数据。

4. 样例模拟（k=3）

$f$数组：
$f[0]=1,\ f[1]=1,\ f[2]=1,\ f[3]=2,\ f[4]=3,\ f[5]=4,\ f[6]=6$

前缀和S数组：
$S_0=1,\ S_1=2,\ S_2=3,\ S_3=5,\ S_4=8,\ S_5=12,\ S_6=18$

• 查询 $[1,3]$：$S_3-S_0 = 5-1=4$
• 查询 $[2,3]$：$S_3-S_1 =5-2=3$
• 查询 $[4,6]$：$S_6-S_3 =18-5=13$

与样例输出完全匹配。