codeforces 474D Flowers ——dp

                                                                             Flowers

input

 standard input

output

 standard output

We saw the little game Marmot made for Mole's lunch. Now it's Marmot's dinner time and, as we all know, Marmot eats flowers. At every dinner he eats some red and white flowers. Therefore a dinner can be represented as a sequence of several flowers, some of them white and some of them red.

But, for a dinner to be tasty, there is a rule: Marmot wants to eat white flowers only in groups of size k.

Now Marmot wonders in how many ways he can eat between a and b flowers. As the number of ways could be very large, print it modulo 1000000007 (109 + 7).

Input

Input contains several test cases.

The first line contains two integers t and k (1 ≤ t, k ≤ 105), where t represents the number of test cases.

The next t lines contain two integers ai and bi (1 ≤ ai ≤ bi ≤ 105), describing the i-th test.

Output

Print t lines to the standard output. The i-th line should contain the number of ways in which Marmot can eat between ai and bi flowers at dinner modulo 1000000007 (109 + 7).

Sample test(s)

input

3 2
1 3
2 3
4 4

output

6
5
5

Note

• For K = 2 and length 1 Marmot can eat (R).
• For K = 2 and length 2 Marmot can eat (RR) and (WW).
• For K = 2 and length 3 Marmot can eat (RRR), (RWW) and (WWR).
• For K = 2 and length 4 Marmot can eat, for example, (WWWW) or (RWWR), but for example he can't eat (WWWR).

一：当在最后一个位置上放R时，前面有多少种与它无关，c[i]=c[i-1]

二：当在最后一个位置上放W时，前面一定放k个w，c[i]=c[i-k]

可得到转移状态方程：dp[i]=dp[i-1]+dp[i-k] 

但是当i<k时，都只能全部放红花，c[i]=1，而且要添加c[0]=1，比如k=2，c[1]=1,c[2]=c[0]+c[1]，所以要令c[0]=1，c数组表示花数为i时，有多少种方式

*题目要求取余 （此题想用dp，从小推大，不要边读边推c[i]，因为这样之前的c[i]可能还没推出就要用到，会出错，应先将所有的c[i]算出，做一个预处理，顺便记录i时，sum[i]=sum[i-1]+c[i]，避免最后又要用循环来记录sum，减少时间）

#define INF 100008
const int  MOD = 1e9 + 7;

#include<algorithm>
#include<iostream>
using namespace std;

struct number
{
	int a, b;
}p[INF];


int main()
{
	int c[INF];  //i朵花时有几种方式
	int sum[INF] = { 0 };
	int t, i, j, k,a, b, Max = -1;
	memset(c, -1000, sizeof(c));
	cin >> t >> k;
	for (i = 0; i < k; i++) {   //题目规定k>1
		c[i] = 1;
		if (i > 0) {
			sum[i] = (sum[i - 1] + c[i]) % MOD;  //i>0
		}
	}
	for (i = 1; i <= t; i++) {
		cin >> p[i].a >> p[i].b;
		if (p[i].b > Max) {
			Max = p[i].b;
		}
	}
	for (i = k; i <= Max; i++) {  
		c[i] = (c[i - k] + c[i - 1]) % MOD;  //主要max不要重复定义
		sum[i] = (sum[i - 1] + c[i])%MOD;
    }
	for (i = 1; i <= t; i++) {
		cout << (sum[p[i].b]-sum[p[i].a-1]+MOD)%MOD<< endl;     //不是花的数目多，方式就一定更多，避免负数，加上MOD
	}
	return 0;
}

结果：