474D - Flowers - CodeForces Solution

#include <bits/stdc++.h>
#define ll long long 
#define mod 1000000007
using namespace std;

void solve(ll k , vector<ll>& dp , vector<ll>& dp2) {
    ll ans = 0;
    ll a , b;
    cin >> a >> b;
    // for(ll i = k ; i <= 100000 ; i++) {
    //     cout << dp2[i] << " ";
    // }
    // cout << dp2[99613] << "    " << dp2[95515] << endl;
    // cout << dp2[93494] - dp2[58867] << endl;
    ans = (dp2[b] - dp2[a - 1])%mod;
    cout << ans%mod << endl;
}

int main() {
    ll t , k;
    cin >> t >> k;
    // t = 1;
    vector<ll>dp(100001 , 1) , dp2(100001 , 0);
    for(ll i = k ; i <= 100000 ; i++) {
        dp[i] = (dp[i - 1] + dp[i - k])%mod;
    }
    for(ll i = 0 ; i <= 100000 ; i++) {
        if(i == 0) {
            dp2[i] = dp[i];
        }
        else {
            dp2[i] += (dp[i] + dp2[i - 1]);
        }
    }
    while (t--) {
        solve(k , dp , dp2);
    }
    return 0;
}