Codeforces Round #271 (Div. 2) D. Flowers（DP）

题目地址：http://codeforces.com/problemset/problem/474/D

思路：f[i]表示长度为i时的方案数，当0<=i<=k时，显然f[i]=1；当i>=k时，f[i]可以是f[i-1]加上一朵红花，也可以是f[i-k]加上k朵白花。

即f[i]=f[i-1]+f[i-k]，求前缀和，则区间 [a,b] 内方案数为sum[b]-sum[a-1]。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=1e5+50;
const LL mod=1e9+7;
struct Node
{
    int l,r;
};
int t,k;
Node a[maxn];
int maxx;
LL sum[maxn],f[maxn];
void prepare()
{
    for(int i=0;i<=maxx;i++)
    {
        if(i<k) f[i]=1;
        else
        {
            f[i]=(f[i-1]+f[i-k]);
           f[i]%=mod;
        }
        //cout<<f[i]<<endl;
    }
    for(int i=0;i<=maxx;i++)
    {
        sum[i]=(sum[i-1]+f[i]);
        //cout<<sum[i]<<endl;
    }
}
int main()
{
    while(scanf("%d%d",&t,&k)!=EOF)
    {
        maxx=0;
        for(int i=0;i<t;i++)
        {
            scanf("%d%d",&a[i].l,&a[i].r);
            maxx=max(a[i].r,maxx);
        }
        prepare();
        for(int i=0;i<t;i++)
        {
           //cout<<sum[a[i].r]<<" "<<sum[a[i].l-1]<<endl;
            printf("%I64d\n",(sum[a[i].r]-sum[a[i].l-1])%mod);
        }
    }
    return 0;
}