链接：https://ac.nowcoder.com/acm/contest/20323/A

来源：牛客网

白云在操场上运动。

白云每秒可以走1米或跑k米。

由于白云很累，它不能连续运行两秒或更长时间。

白云将从L移动到R米。它想知道有多少种不同的方式来实现它的目标。

两种方式是不同的，当且仅当他们移动不同的米或花费不同的秒，或者在一秒钟内，其中一种走，另一种跑。

输入描述:

输入的第一行包含2个整数Q和k。Q是查询数。（Q<=100000,2<=k<=100000）

对于接下来的Q行，每行包含两个整数L和R。（1<=L<=R<=100000）

输出描述:

对于每个查询，打印一行，其中包含一个整数，表示以100000007为模的查询的答案。

示例1 输入 复制 3 3 3 3 1 4 1 5 输出 复制 2 7 11

思路和心得：

(一)dp+前缀和

1.dp 2.前缀和 预计算所有的 查询的时候，需要哪段就查找哪段。

python3 代码

M = 10 ** 5 + 5        #最大的空间
MOD = 10 ** 9 + 7 

dp = [0 for _ in range(M)]

Q, k = map(int, input().split())

for i in range(k):
    dp[i] = 1
dp[k] = 2
for i in range(k + 1, M):
    dp[i] = (dp[i - 1] + dp[i - 1 - k]) % MOD

presum = [0 for _ in range(M)]
presum[0] = 1
for i in range(1, M):
    presum[i] = (presum[i - 1] + dp[i]) % MOD

for _ in range(Q):
    L, R = map(int, input().split())
    res = (presum[R] - presum[L - 1] + MOD) % MOD
    print(res)

c++代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <assert.h>
// #include <bits/stdc++.h>

using namespace std;

const int M = 1e5 + 5;
const int MOD = 1e9 + 7;
long long dp[M];

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int Q;    cin >> Q;
    int k;    cin >> k;
    
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < k; i ++){
        dp[i] = 1;
    }
    dp[k] = 2;
    for (int i = k + 1; i < M; i ++){
        dp[i] = (dp[i - 1] + dp[i - 1 - k]) % MOD;
    }
    
    int presum[M];
    presum[0] = 1;
    for (int i = 1; i < M; i ++){
        presum[i] = (presum[i - 1] + dp[i]) % MOD;
    }
    
    for (int _ = 0; _ < Q; _ ++)
    {
        int L;    cin >> L;
        int R;    cin >> R;
        int res = (presum[R] - presum[L - 1] + MOD) % MOD;
        cout << res << endl;
        
    }
    
    return 0;
}

java代码

import java.util.*;
import java.io.*;

public class Main
{
    static final int M = (int)(1e5 + 5);
    static final int MOD = (int)(1e9 + 7);
    static long [] dp = new long [M];
    
    public static void main(String args[]) throws Exception
    {
        BufferedReader BR = new BufferedReader(new InputStreamReader(System.in));
        String [] line1 = BR.readLine().split(" ");
        int Q = Integer.parseInt(line1[0]);
        int k = Integer.parseInt(line1[1]);
        
        for (int i = 0; i < k; i ++){
            dp[i] = 1;
        }
        dp[k] = 2;
        for (int i = k + 1; i < M; i ++){
            dp[i] = (dp[i - 1] + dp[i - 1 - k]) % MOD;
        }
        
        int [] presum = new int [M];
        presum[0] = 1;
        for (int i = 1; i < M; i ++){
            presum[i] = (presum[i - 1] + (int)dp[i]) % MOD;
        }
        
        for (int ee = 0; ee < Q; ee ++)
        {
            String [] line2 = BR.readLine().split(" ");
            int L = Integer.parseInt(line2[0]);
            int R = Integer.parseInt(line2[1]);
            int res = (presum[R] - presum[L - 1] + MOD) % MOD;
            System.out.println(res);
        }
    }
}