474D. Flowers - Codeforces Solution C++

➤  Problem Link : 474D. Flowers 

✅ C++ Solution :

 
#include<bits/stdc++.h>
using namespace std;

#define ll long long int
ll m=pow(10,9)+7;

int main()
{
	int t,k,a,b;
	cin>>t>>k;
	pair<ll,ll> dp[100001];
	dp[0]=make_pair(1,0);
	for(int i=1;i<=100000;i++)
	{
		if(i<k)
			dp[i]=dp[i-1];
		else
		{
			dp[i].first=(dp[i-1].first+dp[i-1].second)%m;
			dp[i].second=(dp[i-k].first+dp[i-k].second)%m;
		}
	}

	ll cum[100001];
	cum[1]=(dp[1].first+dp[1].second)%m;
	for(int i=2;i<=100000;i++)
		cum[i]=(dp[i].first+dp[i].second+cum[i-1])%m;

	while(t--)
	{
		cin>>a>>b;
		cout<<(cum[b]-cum[a-1]+m)%m<<"\n";
	}

}

 

Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook. 

😇Happy Learning!!

• Tweet
• Share
• Share
• Share
• Share

About Utkarsh Gupta

I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.