[编程题]run
White Cloud is exercising in the playground.
White Cloud can walk 1 meters or run k meters per second.
Since White Cloud is tired,it can't run for two or more continuous seconds.
White Cloud will move L to R meters. It wants to know how many different ways there are to achieve its goal.
Two ways are different if and only if they move different meters or spend different seconds or in one second, one of them walks and the other runs.


输入描述:
The first line of input contains 2 integers Q and k.Q is the number of queries.(Q<=100000,2<=k<=100000)
For the next Q lines,each line contains two integers L and R.(1<=L<=R<=100000)


输出描述:
For each query,print a line which contains an integer,denoting the answer of the query modulo 1000000007.
示例1

输入

3 3
3 3
1 4
1 5

输出

2
7
11
头像 大桔骑士v
发表于 2019-09-15 16:53:28
题目要求的是从l到r的每个位置w,从0走到w的位置总数再全部加起来。 因为不能连续跑两次,也就是如果这次跑了,那上次一定是走。但是这次如果是走,那上次可以是跑的也可以是走的。 详细思路见代码中注释: #include<bits/stdc++.h> using namespace std; 展开全文
头像 XingHe_XingHe
发表于 2021-10-02 17:11:33
链接:https://ac.nowcoder.com/acm/contest/20323/A 来源:牛客网 白云在操场上运动。 白云每秒可以走1米或跑k米。 由于白云很累,它不能连续运行两秒或更长时间。 白云将从L移动到R米。它想知道有多少种不同的方式来实现它的目标。 两种方式是不同的,当且仅当他们 展开全文