D. Flowers
一个简单线性dp
#include <bits/stdc++.h>using namespace std;#define int long longconst int mod = 1e9 + 7;int a[(int)2e6];signed main(){int t, k;cin >> t >> k;a[0] = 1;for (int i = 1; i <= 1e5 + 5; i++){a[i] = a[i - 1];a[i] %= mod;if (i >= k)a[i] += a[i-k];a[i] %= mod;}for (int i = 1; i <= 1e5; i++){a[i] = (a[i] + a[i - 1]) % mod;}int A, B;while (t--){cin >> A >> B;cout << (a[B] - a[A - 1] + mod) % mod << endl;}}
