C++(clang++ 11.0.1) 解法, 执行用时: 284ms, 内存消耗: 2928K, 提交时间: 2022-12-22 22:25:57

#include<iostream>
using namespace std;
int main()
{
	long long b[100001],sum[100001];
	int q,k,x,y;
	cin>>q>>k;
	b[0]=1,sum[0]=0;
	for(int i=1;i<k;i++)
	b[i]=1;
	b[k]=2;
	for(int i=k+1;i<100001;i++)
	b[i]=b[i-1]+b[i-k-1];
	for(int i=1;i<100001;i++)
	sum[i]=sum[i-1]+b[i];
	for(int i=0;i<q;i++)
	{
		cin>>x>>y;
		cout<<(sum[y]-sum[x-1])%1000000007<<endl;
	}
	return 0;
}

Python3(3.5.2) 解法, 执行用时: 639ms, 内存消耗: 8588K, 提交时间: 2018-07-21 12:41:01

dp = [0]*100005
n, k = map(int, input().split())
for i in range(k+1):
    dp[i] = 1
dp[k] = 2
for i in range(k+1, 100005):
    dp[i] = (dp[i-1]+dp[i-k-1]) % 1000000007
for i in range(1, 100005):
    dp[i] += dp[i-1]
for _ in range(n):
    ans = 0
    L, R = map(int, input().split())
    print((dp[R]-dp[L-1]) % 1000000007)