Codeforces Round #271 (Div. 2)D(递推，前缀和)

很简单的递推题。d[n]=d[n-1]+d[n-k]

注意每次输入a和b时，如果每次都累加，就做了很多重复性工作，会超时。

所以用预处理前缀和来解决重复累加问题。

最后一个细节坑了我多次：

printf("%I64d\n",(s[b]-s[a-1]+mod)%mod);

这句话中加mod万万不能少，因为理论上s[b]-s[a-1]肯定大于0，但是由于两个都是模1000000007以后的结果，那么就不一定了，当s[b]-s[a-1]<0时结果是负的，不是题意中应该输出的结果，所以一定要加mod。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<map>

#include<set>

#include<vector>

#include<algorithm>

#include<stack>

#include<queue>

#include<cctype>

#include<sstream>

using namespace std;

#define INF 1000000000

#define eps 1e-8

#define pii pair<int,int>

#define LL long long int

#define mod 1000000007

LL t,k,a,b,d[],s[];

int main()

{

    //freopen("in8.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    scanf("%I64d%I64d",&t,&k);

    for(int i=;i<k;i++) d[i]=;

    d[k]=;

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

    {

        d[i]=(d[i-]+d[i-k])%mod;

    }

    s[]=;

    s[]=d[];

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

    {

        s[i]=(s[i-]+d[i])%mod;

    }

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

    {

        scanf("%I64d%I64d",&a,&b);

        printf("%I64d\n",(s[b]-s[a-]+mod)%mod);

    }

    //fclose(stdin);

    //fclose(stdout);

    return ;

}

巴特西

Codeforces Round #271 (Div. 2)D(递推，前缀和)

最新文章

热门文章