牛客多校第二场A run（基础DP）

链接：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

输入

复制

输出

2
7
11

思路分析:
本题背景抛开，其实就是一个L到R区间内的一个数可以拆成多少种1和K两个数的和
本题最开始想用排列组合做，因为K的不同位置和不同个数。。。引起不同种类，后来发现需要求组合数1-100000，这明显是不切实际的。。。
换种思路：其实用DP的思想想一想，每个状态都是上面两个状态传来，分别是DP[i]=DP[i-1]+DP[i-K],但是不要着急。。。很明显题意给了一个限制条件，不能连续的跑
我们可以用一个DP[i][3]来表示各个状态
   首先DP[i][0]代表走路到这个位置
      DP[i][1]代表跑步到这个位置
      DP[i][2]代表到这个位置的所有种类
   这样我们就可以写出转移方程
      DP[i][0]=DP[i-1][2]
      DP[i][1]=DP[i-k][0]
      DP[i][2]=DP[i][0]+DP[i][1]
   当然有大神找规律得出这个动态转移方程
      DP[i]=DP[i-1]+DP[i-K-1]
   是不是很6？？？仔细想想其实也是对的，我们由于不能直接从DP[i-K]因为不能连续的跑步，我们知道DP[i-K-1]肯定是走路到DP[i-k]那么其实直接用DP[i-K-1]
就好了，最后前缀和数保存就行
   最后一定要注意取模的地方。。。
(a+b) mod p = (a mod p + b mod p) mod p 
(a*b) mod p = ((a mod p) * (b mod p)) mod p 
(a-b) mod p = ((a mod p)-(b mod p) + p) mod p 
所以取模应该是
ans=(DP[r]-DP[l-1]+mod)%mod
代码如下

#include<iostream>
#include<string.h>
#include<stdio.h>
#define ll long long
using namespace std;
const int N = 100000+7;
const int mod = 1000000007;
ll dp[N][3];
ll sum[N];
int main(){
  int q,k;
  while(~scanf("%d%d",&q,&k)){
      sum[0]=0;
      dp[0][0]=1;
      dp[k][1]=1;
      dp[0][2]=1;
      for (int i=1;i<=100000;i++){
         dp[i][0]=dp[i-1][2];
         if(i-k>=0){
            dp[i][1]=dp[i-k][0];
         }
         dp[i][2]=(dp[i][1]+dp[i][0])%mod;
         sum[i]=(sum[i-1]+dp[i][2])%mod;
      }
      int l,r;
      ll ans=0;     
      for(int i=1;i<=q;i++){
         scanf("%d%d",&l,&r);
         ans=(sum[r]%mod-sum[l-1]+mod)%mod;
         printf("%lld
",ans);
      }
  }
  return 0;
}

View Code