题意

将每个字符串表示为二进制串（用 $0$ 和 $1$ 代替红白花）。一个字符串是“好”的，当且仅当每个由连续 $0$ 组成的极长子串的长度都能被 $k$ 整除。

思路

使用动态规划求解。定义 $nr_i$ 表示长度为 $i$ 的好字符串的数量。

• 如果第 $i$ 个字符是 $1$，则前面的字符可以任意，因此方案数为 $nr_{i-1}$。
• 如果第 $i$ 个字符是 $0$，则它必须与前面的 $k-1$ 个 $0$ 连续出现，因此方案数为 $nr_{i-k}$。
  于是得到递推式：

算法步骤

1. 预处理 $nr$ 数组，长度为最大可能的 $b_i$（记为 $maxVal$）。
2. 计算前缀和 $sum_i = nr_1 + nr_2 + \dots + nr_i$。
3. 对于每个询问 $(a, b)$，答案为 $sum_b - sum_{a-1}$。

复杂度分析

• 时间复杂度：$O(maxVal + t)$，其中 $maxVal$ 是所有 $b_i$ 的最大值，$t$ 是询问次数。
• 空间复杂度：$O(maxVal)$。

代码说明

• 先读入 $k$ 和 $t$，以及所有询问，找出最大的 $b_i$。
• 初始化 $nr_0 = 1$，然后按递推式计算 $nr_1$ 到 $nr_{maxVal}$。
• 计算前缀和数组 $sum$。
• 对每个询问输出 $sum_b - sum_{a-1}$。

#include<bits/stdc++.h>
using namespace std;
#define PF 1000000007
#define MAXN 100005
long long n,k,f[MAXN]={0},s[MAXN]={0},a,b; //long long
int main(){
    cin>>n>>k;
    f[0]=1;//初始化
    for(int i=1;i<=MAXN;i++) { //dp
        f[i]+=f[i-1]%PF;
        if(i>=k)f[i]+=f[i-k]%PF;
        s[i]=(s[i-1]+f[i])%PF; //前缀和
    }
    for(int i=1;i<=n;i++) {
        cin>>a>>b;
        cout<<(s[b]-s[a-1]+PF)%PF<<endl; //输出
    }
}