codeforces474D

Flowers

CodeForces - 474D

话说某个幸运的小伙伴X拿到了kevin女神送的蛋糕，然而他的吃法非常奇特，他独创了两种吃蛋糕的办法：一、一次吃一整个蛋糕；二、一次吃k个蛋糕。

那么，当蛋糕数量为x1到x2之间时，一共能有几种不同的吃法呢？

由于答案很大，输出结果mod 1000000007的值

Input

第一行有两个正整数t,k(1<=t,k<=100000) ，其中t表示数据的组数。

接下来t行，每行两个数x1, x2(1<=x1<=x2<=100000)。

Output

共t行，每行一个正整数x，表示蛋糕数量在x1-x2之间时，一共能有几种不同的吃法，结果对(10^9+7)取模

Sample Input

3 2

1 3

2 3

4 4

Sample Output

Hint

样例中，k=2

我们标记吃法1为A，吃法2为B

当蛋糕数为1时，共1种吃法即为A

当蛋糕数为2时，共2种，分别为 AA,B

当蛋糕数为3时，共3种，分别为 AAA,AB,BA

当蛋糕数为4时，共5种，分别为 AAAA, AAB,ABA,BAA,BB

sol：开始以为是组合数一样的东西，搞了一会后严重自闭，发现是dp。。。

dp[i]表示蛋糕数量为 i 的吃法，对dp记个前缀和就可以O(1)查询了

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

inline ll read()

{

    ll s=;

    bool f=;

    char ch=' ';

    while(!isdigit(ch))

    {

        f|=(ch=='-'); ch=getchar();

    }

    while(isdigit(ch))

    {

        s=(s<<)+(s<<)+(ch^); ch=getchar();

    }

    return (f)?(-s):(s);

}

#define R(x) x=read()

inline void write(ll x)

{

    if(x<)

    {

        putchar('-'); x=-x;

    }

    if(x<)

    {

        putchar(x+''); return;

    }

    write(x/);

    putchar((x%)+'');

    return;

}

#define W(x) write(x),putchar(' ')

#define Wl(x) write(x),putchar('\n')

const ll Mod=;

const int N=;

int T;

ll K;

ll Qzh[N];

ll dp[N];

int main()

{

    int i,j;

    R(T); R(K);

    dp[]=Qzh[]=;

    for(i=;i<=;i++)

    {

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

        if(i>=K) dp[i]+=dp[i-K];

        dp[i]-=(dp[i]>=Mod)?Mod:;

        Qzh[i]=Qzh[i-]+dp[i];

        Qzh[i]-=(Qzh[i]>=Mod)?Mod:;

    }

    while(T--)

    {

        int l=read(),r=read();

        Wl((Qzh[r]-Qzh[l-]+Mod)%Mod);

    }

    return ;

}

/*

input

3 2

1 3

2 3

4 4

output

6

5

5

*/

巴特西

codeforces474D

Flowers

最新文章

热门文章