牛客网暑期ACM多校训练营(第二场) A run

  • 2018-07-21
  • 12
  • 0

题目:

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.

Input:

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)

Output:

For each query,print a line which contains an integer,denoting the answer of the query modulo 1000000007.

Sample Input:

3 3
3 3
1 4
1 5

Sample Output:

2
7
11

题目链接

White Cloud一秒内可以走路一米或者跑k米,但是不能连续奔跑两秒及以上,对每次询问l,r输出White Cloud从0点到达[l,r]内所有点的不同抵达方式种类数之和。

先对从0出发到最大值进行打表,dp[i][0]代表最后是走路抵达i点的种类数,dp[i][1]代表最后是跑步抵达i点的种类数。dp[i][0]等于最后是走路抵达i-1的种类数与最后是跑步抵达i-1的种类数之和,dp[i][1]等于最后是走路抵达i-k点的种类数(不能加最后是跑步抵达i-k的种类数,因为不能连续奔跑)。之后用一个数组ans[i]记录前i个点所有抵达方式只和,每次对询问区间取(ans[r] – ans[l – 1]) % mod即为最终结果。

AC代码:

评论

还没有任何评论,你来说两句吧