A题题解

A题

A题描述

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.

A输入描述

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)

A输出描述

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

A输入

A输出

1
2
3

2
7
11

A题分析

看完题目第一反应是用深度优先搜索找出所有的情况并给出答案，将写出的代码提交后发现超时了。

第二个想法就是找规律，利用最初写好的深搜代码，得到多组数据，再对这些数据找规律后发现f(n)=f(n-1)+f(n-k-1)其中K为跑步的速度，n是白云到第n个点的方法。

AC代码A

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define lowbit(i) ((i) & (-i))

#define MOD 1000000007

using namespace std;
int q, k;
long long A[100007];
long long B[100007] = {0};
void gettime();
int main()
{
    scanf("%d%d", &q, &k);
    gettime();
    for (int i = 0, l, r; i < q; ++i)
    {
        scanf("%d%d", &l, &r);
        printf("%d\n", (int)((B[r] - B[l - 1]) % MOD));
    }
    return 0;
}

void gettime()
{
    for (int i = 1; i < k; i++)
    {
        A[i] = 1;
    }
    A[k] = 2;
    A[k + 1] = 3;
    for (int i = k + 2; i <= 100000; i++)
    {
        A[i] = A[i - (k + 1)] + A[i - 1];
    }
    for (int i = 1; i <= 100000; ++i)
    {
        B[i] = A[i] + B[i - 1];
    }
}