题目链接：http://codeforces.com/problemset/problem/474/D
题目意思：Marmot 吃两种类型的花（实在难以置信呀～～）：red 或者 white，如果要吃到white这种花，就需要吃连续 k 朵 white；而如果吃 red，就没有这种限制。给定区间[a, b]，问总共的吃法有多少种。
dp 题！状态转移方程不难得到。设 dp[i] 表示 长度为 i 时 的吃法种数。
dp[i] = dp[i-1] + dp[i-k]
对于当前 i，或者是从第 i-1 条长度后直接添加 red，又或者 在 i-k 的长度后添加 white。这两种情况都添加完之后长度都变为 i 了。
不过有个数学问题错了 n 次。当大于 1e9+7时，需要减去 1e9 + 7。还有，处理dp的值时要离线处理，否则TLE。这意味着要用多一个数组sum。
sum[i]表示长度为到达长度为 i 时一共的吃法种数（有点拗口），与dp[i]是不同的，是累加呀～～～
话说我是看了tourist 对 这个 1e9+7 的处理才改对的。他代码非常精简：
http://codeforces.com/submissions/tourist
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std; const int MOD = 1e9+;
const int maxn = 1e5 + ; int dp[maxn], sum[maxn]; int main()
{
int t, k, a, b;
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
while (scanf("%d%d", &t, &k) != EOF)
{
memset(dp, , sizeof(dp));
memset(sum, , sizeof(sum)); for (int i = ; i <= k; i++) // 前 k 个长度只能不断添加R这种花
{
dp[i]++;
sum[i] = sum[i-] + dp[i];
}
dp[k]++; // 到达 k 这个长度表示可以添加第一个W这种花了
sum[k]++; // 加多一种只吃 W 的情况 for (int i = k+; i <= maxn; i++)
{
dp[i] = (dp[i-k] + dp[i-]);
dp[i] = (dp[i] >= MOD ? dp[i]-MOD : dp[i]); sum[i] = (sum[i-] + dp[i]);
sum[i] = (sum[i] >= MOD ? sum[i]-MOD : sum[i]);
} while (t--)
{
scanf("%d%d", &a, &b);
printf("%d\n", (sum[b]-sum[a-]+MOD) % MOD); // 这个很关键
}
}
return ;
}