474D codeforces - Flowers
Solution in C++
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
#define pii pair<int,int>
lli n,k,t1,t2,mod=1000000007,dp[100005],sol[100005];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>k;
for(int i=0;i<=100005;i++)dp[i]=((i<k)?1:dp[i-1]+dp[i-k]),dp[i]%=mod;
dp[0]=0;
for(int i=2;i<=100005;i++)dp[i]=(dp[i-1]+dp[i])%mod;
while(n-- && cin>>t1>>t2)cout<<(dp[t2]-dp[t1-1]+mod)%mod<<"\n";
return 0;
}
inulti-za John Davies Here
ردحذفbentipichi