A93777 拼花带 解题报告 1. 题意分析 红色花带片长度为 111，白色花带片长度为 kkk。 f(n)f(n)f(n) 表示恰好拼成长度 nnn 的不同拼法数量。 现有 ttt 次询问，每次给出区间 [a,b][a,b][a,b]，求： ∑n=abf(n)(mod109+7)\sum_{n=a}^{b} f(n) \pmod{10^9+7} n=a∑b f(n)(mod109+7) 数据范围 * 1≤t,k≤1051 \le t,k \le 10^51≤t,k≤105 * 1≤ai≤bi≤1051 \le a_i \le b_i \le 10^51≤ai ≤bi ≤105 样例说明（k=3k=3k=3）： * f(0)=1f(0)=1f(0)=1：空拼法，作为递推基准 * f(1)=1, f(2)=1f(1)=1,\ f(2)=1f(1)=1, f(2)=1 * f(3)=f(2)+f(0)=2f(3)=f(2)+f(0)=2f(3)=f(2)+f(0)=2 * f(4)=f(3)+f(1)=3f(4)=f(3)+f(1)=3f(4)=f(3)+f(1)=3 * f(5)=f(4)+f(2)=4f(5)=f(4)+f(2)=4f(5)=f(4)+f(2)=4 * f(6)=f(5)+f(3)=6f(6)=f(5)+f(3)=6f(6)=f(5)+f(3)=6 2. 递推公式推导 凑成长度 nnn 有两种选择： 1. 最后放红色花带（长度1）：前面拼出 n−1n-1n−1，方案数 f(n−1)f(n-1)f(n−1) 2. 最后放白色花带（长度k）：仅当 n≥kn \ge kn≥k，前面拼出 n−kn-kn−k，方案数 f(n−k)f(n-k)f(n−k) 递推式： {f(0)=1f(n)=f(n−1)1≤n<kf(n)=f(n−1)+f(n−k)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} ⎩⎨⎧ f(0)=1f(n)=f(n−1)f(n)=f(n−1)+f(n−k) 1≤n<kn≥k 定义前缀和数组 S[n]=∑i=0nf(i) mod (109+7)S[n]=\sum_{i=0}^{n}f(i) \bmod (10^9+7)S[n]=∑i=0n f(i)mod(109+7)。 对于查询区间 [a,b][a,b][a,b]： ans=(S[b]−S[a−1]+MOD) mod MODans = (S[b]-S[a-1] + \text{MOD}) \bmod \text{MOD} ans=(S[b]−S[a−1]+MOD)modMOD > 加上 MOD 再取模，避免减法得到负数。 3. 算法复杂度 * DP预处理：O(MAX)O(\text{MAX})O(MAX)，MAX=105\text{MAX}=10^5MAX=105 * 前缀和预处理：O(MAX)O(\text{MAX})O(MAX) * 每次查询 O(1)O(1)O(1)，全部查询 O(t)O(t)O(t) * 总复杂度 O(105+t)O(10^5 + t)O(105+t)，可以通过全部数据。 4. 样例模拟（K=3） fff数组： f[0]=1, f[1]=1, f[2]=1, f[3]=2, f[4]=3, f[5]=4, f[6]=6f[0]=1,\ f[1]=1,\ f[2]=1,\ f[3]=2,\ f[4]=3,\ f[5]=4,\ f[6]=6f[0]=1, f[1]=1, f[2]=1, f[3]=2, f[4]=3, f[5]=4, f[6]=6 前缀和S数组： S0=1, S1=2, S2=3, S3=5, S4=8, S5=12, S6=18S_0=1,\ S_1=2,\ S_2=3,\ S_3=5,\ S_4=8,\ S_5=12,\ S_6=18S0 =1, S1 =2, S2 =3, S3 =5, S4 =8, S5 =12, S6 =18 * 查询 [1,3][1,3][1,3]：S3−S0=5−1=4S_3-S_0 = 5-1=4S3 −S0 =5−1=4 * 查询 [2,3][2,3][2,3]：S3−S1=5−2=3S_3-S_1 =5-2=3S3 −S1 =5−2=3 * 查询 [4,6][4,6][4,6]：S6−S3=18−5=13S_6-S_3 =18-5=13S6 −S3 =18−5=13 与样例输出完全匹配。