牛客多校第二場 A run

連結：https://www.nowcoder.com/acm/contest/140/A

來源：牛客網

時間限制：C/C++ 1秒，其他語言2秒

空間限制：C/C++ 131072K，其他語言262144K

64bit IO Format: %lld

題目描述

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.

輸入描述:

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)      

輸出描述:

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

示例1

輸入

複制

3 3
3 3
1 4
1 5      

輸出

複制

2
7
11
      

題意：一個人可以選擇一次走1m或者選擇一次跑k m，問從L跑到R有多少種方法；

思路：dp推導，dp[i][0]表示走i米的方法數，dp[i][1]表示跑到第i米所表示的方法數，那麼到第i米走着來的所用的方法數可以由第i-1米走着來的和跑着來的方法數得到，那麼第i米跑着來的方法數可以由第i-k米的方法數得到，這樣就得到一個遞推式：

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

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

然後我們用一個數組sum記錄字首和，那麼從L到R的方法數等于sum[r]-sum[l-1]，注意取餘即可；

下面附上代碼：

#include<bits/stdc++.h>
using namespace std;
const int mod=1000000007;
int dp[100005][2];
int sum[100005];
int n,q,k,l,r;
void solve()
{
    dp[0][0]=1;
    for(int i=1;i<=1e5;i++)
    {
        dp[i][0]=(dp[i-1][0]%mod+dp[i-1][1]%mod)%mod;
        if(i>=k) dp[i][1]=dp[i-k][0]%mod;
    }
    for(int i=1;i<=1e5;i++)
        sum[i]=(sum[i-1]%mod+dp[i][0]%mod+dp[i][1]%mod+mod)%mod;
}l;
int main(){
    cin>>q>>k;
    solve();
    while(q--)
    {
        scanf("%d %d",&l,&r);
        printf("%d\n",(sum[r]-sum[l-1]+mod)%mod);
    }
    return 0;
}
           

凱哥的：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
ll dp[100005][5];
ll dpp[100005];
int main()
{
    ll Q,k;
     
    while(~scanf("%lld %lld",&Q,&k)){
        ll L,R;
        memset(dp,0,sizeof(dp));
        memset(dpp,0,sizeof(dpp));
        for(ll i=1;i<=k;i++){
            dp[i][1]=1;
            dp[i][0]=0;
        }
        dp[k][0]=1;
        for(ll i=1;i<=k;i++){
            dpp[i]=(dp[i][1]+dp[i][0][phone])%1000000007;
        }
        /*
        dp[1][1]=1;
        dp[1][3]=0;
        dpp[1]=1;
        dp[2][1]=1;
        dp[2][3]=0;
        dpp[2]=1;
        dp[3][1]=1;
        dp[3][3]=1;
        dpp[3]=2;
        */
        for(ll i=k+1;i<=100002;i++){
            dp[i][1]=(dp[i-1][1]+dp[i-1][0][phone])%1000000007;
            dp[i][0]=dp[i-k][1];
            dpp[i]=(dp[i][1]+dp[i][0][phone])%1000000007;
        }
        //printf("----\n");
        //for(int i=1;i<=7;i++){
        //  printf("%d ",dpp[i]);
        //}
        //printf("----\n");
        for(ll i=2;i<=100002;i++){
            dpp[i]=(dpp[i]+dpp[i-1][phone])%1000000007;
        }
 
        while(Q--){
            scanf("%lld%lld",&L,&R);
            printf("%lld\n",(dpp[R]-dpp[L-1][phone])%1000000007);
        }
         
    }
     
    return 0;
}