Codeforces 474D

474D - Flowers

思路：dp.

dp[i]表示长度为i的方案数

显然，当i<k时，dp[i]=1

当i>=k时，dp[i]可以由dp[i-1]加上一朵红花转移过来，由dp[i-k]加上k朵白花转移过来，所以dp[i]=dp[i-1]+dp[i-k]

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a))

const int MOD=1e9+7;
const int N=1e5+5;
int dp[N];
ll sum[N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t,k,a,b;
    cin>>t>>k;
    dp[0]=1;
    for(int i=1;i<k;i++)dp[i]=1;
    for(int i=k;i<N;i++){
        dp[i]=(dp[i-1]+dp[i-k])%MOD;
    }
    for(int i=1;i<N;i++)sum[i]=(sum[i-1]+dp[i])%MOD;
    while(t--){
        cin>>a>>b;
        cout<<((sum[b]-sum[a-1])%MOD+MOD)%MOD<<endl;
    }
    return 0;
}