Решение задачи Цветы с Codeforces

Без пояснения   Просмотров: 34


Мы видели маленькую игру, которую Сурок приготовил для Крота на обед. Теперь Сурку пора ужинать — а мы все знаем, что Сурок ест цветы. За каждым ужином он ест немного красных и немного белых цветов. Таким образом, ужин можно представить как последовательность белых и красных цветов.

Но для того, чтобы ужин был вкусный, есть одно правило: когда Сурок хочет отведать белых цветов, он потребляет их только группами размера k.

Теперь Сурку интересно, сколько существует способов съесть от a до b цветов по его правилам. Так как количество способов может быть очень большим, выведите его по модулю 1000000007 (109 + 7).

Код

#include<bits/stdc++.h>
using namespace std;
long long t,k,l,r,a[200000]={1},mod=1e9+7;
int main()
{
	cin >> t >> k;
	for(int i = 1; i <= 1e5; i++)
	{
		if(i < k)
			a[i] = a[i - 1];
		else
			a[i] = (a[i - 1] + a[i - k]) % mod;
		// cerr<<a[i]<<' ';
	}
	for(int i = 1; i <= 1e5; i++)
		a[i] = (a[i] + a[i - 1]) % mod;
	// cout<<endl;
	while(t--)
	{
		cin >> l >> r;
		cout<<(a[r] - a[l - 1] + mod) % mod<<endl;
	}
	return 0;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться