牛客多校第二場A

題目大意：

一個人可以走1步或跑k步，但不能連續跑2秒或以上，求解到達l-r的方法總數

題目分析：

對于最後一步的狀态進行讨論

         如果是跑的話，證明上一個狀态隻能由走來推出

         如果是走的話，則可以由上一個狀态的走和跑來推出

         由以上可以建立dp方程

         dp[i][0]=dp[i-1][1]+dp[i-1][0];

         dp[i][1]=dp[i-1][0];

代碼：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+50;
long long int dp[maxn][2],ans[maxn];
const int mod=1e9+7;
int main()
{
    int q,k;
    while(~scanf("%d%d",&q,&k))
    {
        memset(dp,0,sizeof(dp));
        dp[0][0]=1;
        for(int i=1;i<maxn;i++)
        {
            if(i>=k)dp[i][1]=dp[i-k][0];
            dp[i][0]=(dp[i-1][0]+dp[i-1][1])%mod;
        }
        for(int i=1;i<maxn;i++)
        {
            dp[i][0]=(dp[i][1]+dp[i][0]+dp[i-1][0])%mod;
        }
        while(q--)
        {
            //dp[0][0]=0;
            int l,r;
            scanf("%d%d",&l,&r);
            printf("%lld\n",(dp[r][0]-dp[l-1][0]+mod)%mod);
        }
    }
}