题目描述

给定一个整数 k。

现在，我们可以对 01 字符串进行如下操作：

选择其中恰好 k 个连续的 1，将它们都变为 0。

如果一个 01 字符串可以通过若干次上述操作，变为一个全 0 字符串，那么就称这个字符串很优秀。

本题共需要回答 T 组询问，每组询问给定两个整数 l,r，并请你计算长度在 [l,r] 范围内的所有 01 字符串中优秀字符串的数量

样例

3 2
1 3
2 3
4 4

算法1

(暴力枚举) $O(n^2)$

动态规划+前缀和

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
long long n,k,l,r,dp[111111][2],sr,f[111111];
const int mod = 1e9+7;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    dp[0][0]=1;
    cin >> n >> k;
    for(int i=1;i<=1e5;i++){
        dp[i][0]=(dp[i-1][0]+dp[i-1][1])%mod;
        if(i-k>=0)dp[i][1]=(dp[i-k][0]+dp[i-k][1])%mod;
        f[i]=(f[i-1]+dp[i][0]+dp[i][1])%mod;
    }
    for (int i = 1; i <= n; i ++ ){
        cin >> l >>r;
        cout<<(f[r]-f[l-1]+mod)%mod<<"\n";
    }
}