首页 > 其他 > 详细

CodeForces 474D Flowers

时间:2018-02-20 23:29:20      阅读:241      评论:0      收藏:0      [点我收藏+]

题意:红花k朵相连,白花随意,问长度为L到R区间内,一共有多少种情况;

思路:题目上说了长度,所以状态是与长度有关的,这个题和贴瓷砖的题有点像(简直一模一样),所以直接考虑是装红花还是白花

代码:

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
const int MOD=1e9+7;
int dp[maxn],sum[maxn];
int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=0;i<=maxn;i++){
        dp[i]=1;
    }
    for(int i=k;i<maxn;i++){
        dp[i]=(dp[i-1]+dp[i-k])%MOD;
    }
    sum[0]=0;
    for(int i=1;i<maxn;i++){
        sum[i]=(sum[i-1]+dp[i])%MOD;
    }
    for(int i=0;i<n;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d\n",(sum[r]-sum[l-1]+MOD)%MOD );
    }
    return 0;
}

 

CodeForces 474D Flowers

原文:https://www.cnblogs.com/lalalatianlalu/p/8455998.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!